Date: Mar 7, 2014 8:00 AM
Author: Peter Percival
Subject: Re: 4 colors problem

Peter Percival wrote:
> Arturo Magidin wrote:
>

>> The theorem is **NOT** about "patterns". The theorem does **NOT** say
>> that there is an algorithm for producing a coloring, as you seem to
>> think. The theorem says that **GIVEN** a map, a coloring exists *for
>> that map*.

>
> May I ask if there is a practical algorithm? Clearly there is an
> algorithm: colour the given (finite) map in all possible ways with four
> or fewer colours, examine each colouring in turn until an admissible one
> is found. The theorem ensures that one will be found. But that would
> be quite impractical.


To answer my own question: "Since the proving of the theorem, efficient
algorithms have been found for 4-coloring maps requiring only O(n^2)
time, where n is the number of vertices." is from
http://en.wikipedia.org/wiki/Four_colour_map_problem.

--
Madam Life's a piece in bloom,
Death goes dogging everywhere:
She's the tenant of the room,
He's the ruffian on the stair.