
Re: 4 colors problem
Posted:
Mar 7, 2014 8:00 AM


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 4coloring 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.

