A Machine Resolution of a Four-Color Hoax 6 citations � 0 self

Abstract:  ring algorithm for maps. But it is reasonable to take the approach of first turning the map into a graph, and then use a coloring algorithm for graphs. 2. The Kempe Four-Color Algorithm In 1879 Kempe gave an explicit method of 4-coloring planar maps, which I summarize here from the point of view of planar graphs. Assume a planar graph G is given, with vertices labeled 1 through n; R, G, B, and Y denote the four colors red, green, blue, and yellow. Choose the first vertex in G ---call it v --- having degree 5 or less (it follows quickly from Euler's formulas that every planar graph has such a vertex). Remove it. Color the remaining graph by induction on the vertex set. Then color v as follows: 1. If the neighbors of v have only 3 colors appearing among them, then there is a color left free for v. 2. If there are 4 neighbors of v and all 4 colors appear among them, use a Kempe chain to eliminate one of the colors from the set of neighbors. 3. If there are 5 neighbors of v and all 4 co