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.