Four-Coloring Planar Graphs
Four-Coloring Planar Graphs
The famous four-color theorem, proved in 1976, says that the vertices of any planar graph can be colored in four colors so that adjacent vertices receive different colors. Kempe's method of 1879, despite falling short of being a proof, does lead to a good algorithm for four-coloring planar graphs. The method is recursive. One finds a vertex that has degree at most 5; such exists by Euler's formula for graphs in the plane, , where , , and are the number of vertices, edges, and faces. Then assume the rest of the graph to be properly colored and color by considering three cases:
u
V-E+F=2
V
E
F
u
Case 1. The neighbors of use fewer than four colors: then there is a free color for .
u
u
Case 2. There are four neighbors of and they use all four colors. Then use the Kempe chain method to switch some colors so that only three are used, thus freeing up a color for .
u
u
Case 3. There are five neighbors of and they use all four colors. Then use the Kempe chain method to switch some colors so that only three are used, thus freeing up a color for .
u
u
This Demonstration shows how the algorithm proceeds, starting from the base case of a single vertex and progressing through the recursion until all vertices are colored. For most graphs, such as the random graphs appearing as choices , where is the number of vertices, the method works very well. Kempe thought that the method would always work, but there are examples for which the Kempe chain method fails in Case 3, notably a 17-vertex graph allowed as a choice in this Demonstration. One can still use the method provided one first permutes the vertex order (one such permuted graph is the last choice). Experiments show that for 90% of the permutations, the Kempe impasse in this example disappears.
G(n)
n