Knowing it is always possible to 4 colour a map
motivates the use of simple
heuristic approaches to 4-colouring a given map. For
not too complicated
maps this will usually work within acceptable time
constraints. But in
general for arbitrary maps simple heuristics can take
forever. Hence my
question - which may have an answer well known to
everyone but me.

Has the Proof of the 4 colour map Theorem lead to any
relatively simple
constructive consequences / methodologies ?

I.e. If I have an arbitrary uncoloured map is there a
formula that I (a real
person) can follow that will enable me to
automatically produce a map using
no more than 4 colours ?

I suppose (but don't know for a fact) that it is
possible to write a program
to enable a computer to do the job - but that is as
undesirable as the
original proof.

Knowing it is always possible to 4 colour a map motivates the use of simple
heuristic approaches to 4-colouring a given map.  For not too complicated
maps this will usually work within acceptable time constraints.  But in
general for arbitrary maps simple heuristics can take forever.  Hence my
question - which may have an answer well known to everyone but me.

Has the Proof of the 4 colour map Theorem lead to any relatively simple
constructive consequences / methodologies ?

I.e. If I have an arbitrary uncoloured map is there a formula that I (a real
person) can follow that will enable me to automatically produce a map using
no more than 4 colours ?

I suppose (but don't know for a fact) that it is possible to write a program
to enable a computer to do the job - but that is as undesirable as the
original proof.

On Apr 26, 7:16 am, Terry/Padden <tpad...@bigpond.net.au> wrote:

Knowing it is always possible to 4 colour a map motivates the use of simple
heuristic approaches to 4-colouring a given map. For not too complicated
maps this will usually work within acceptable time constraints. But in
general for arbitrary maps simple heuristics can take forever. Hence my
question - which may have an answer well known to everyone but me.

Has the Proof of the 4 colour map Theorem lead to any relatively simple
constructive consequences / methodologies ?

I.e. If I have an arbitrary uncoloured map is there a formula that I (a real
person) can follow that will enable me to automatically produce a map using
no more than 4 colours ?

Yes there is an algorithm that enables one to color any map using no
more than 4 colours.

1. Use spiral chains of a maximal planar graph.
2. Use spiral chain coloring algorithm to color the graph with no more
than four colors. This part is a bit technical since the use of three-
color classes for the spiral chain segments in order to maintain three-
colorability of the current spiral segment as well as the outer 3-
cycle of the graph (termination conditition of the algorithm).

More you can find from my two arXiv papers (http://arxiv.org/abs/math/
0408247) and (http://arxiv.org/abs/0710.2066).



I suppose (but don't know for a fact) that it is possible to write a program
to enable a computer to do the job - but that is as undesirable as the
original proof.

On 26 Apr, 08:32, ica...@gmail.com wrote:





On Apr 26, 7:16 am, Terry/Padden <tpad...@bigpond.net.au> wrote:

Knowing it is always possible to 4 colour a map motivates the use of simple
heuristic approaches to 4-colouring a given map.  For not too complicated
maps this will usually work within acceptable time constraints.  But in
general for arbitrary maps simple heuristics can take forever.  Hence my
question - which may have an answer well known to everyone but me.

Has the Proof of the 4 colour map Theorem lead to any relatively simple
constructive consequences / methodologies ?

I.e. If I have an arbitrary uncoloured map is there a formula that I (a real
person) can follow that will enable me to automatically produce a map using
no more than 4 colours ?

Yes there is an algorithm that enables one to color any map using no
more than 4 colours.

1. Use spiral chains of a maximal planar graph.
2. Use spiral chain coloring algorithm to color the graph with no more
than four colors. This part is a bit technical since the use of three-
color classes for the spiral chain segments in order to maintain three-
colorability of the current spiral segment as well as the outer 3-
cycle of the graph (termination conditition of the algorithm).

More you can find from my two arXiv papers (http://arxiv.org/abs/math/
0408247) and (http://arxiv.org/abs/0710.2066).

I suppose (but don't know for a fact) that it is possible to write a program
to enable a computer to do the job - but that is as undesirable as the
original proof.

It is obvious that you could write a program to 4-colour a map,
because there are only finitely many possible colourings, so you could
just try them all.

The interesting mathematical question is whether there is a polynomial
time algorithm to 4-colour a map. Do you know whether the algorithm
you refer to above is polynomial?

Derek Holt.- Hide quoted text -

- Show quoted text -

Hi Terry,

I am a programmer, not a mathematician, so hope I won't just add more
confusion to your question. Anyway, here is my 2c, and then maybe someone else
will drop in and give some more sensible answer.

I was a programmer in the 1960's but gave up on Computer Science in the mid

Heuristics are there to _reduce_ the algorithm time, and they by themselves do
not solve any problem. Hmm, I guess one of us here is not getting the point.

Heuristics just means an absence of structured methods. It is just a posh

Again, I'd say it is the other way round. In fact, that "proof" is an
algorithm to show that no counter-counter examples exist. BTW, that is why
that "proof" is so controversial, I suppose: something like a proof by
reductio-ad-reductio... oh, well, hope you get my point.

Indeed, what you can "follow" is an algorithm, not a formula.

Yes there is an algorithm that enables one to color any map using no
more than 4 colours.

1. Use spiral chains of a maximal planar graph.
2. Use spiral chain coloring algorithm to color the graph with no more
than four colors. This part is a bit technical since the use of three-
color classes for the spiral chain segments in order to maintain three-
colorability of the current spiral segment as well as the outer 3-
cycle of the graph (termination conditition of the algorithm).

More you can find from my two arXiv papers (http://arxiv.org/abs/math/
0408247) and (http://arxiv.org/abs/0710.2066).