9711

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:
Case 1. The neighbors of use fewer than four colors: then there is a free color for .
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 .
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 .
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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Snapshot 1. Kempe's method always works in the four-neighbor case. In this 15-vertex example the colors of vertices 4 and 6 can be switched (a yellow-green Kempe chain), which frees up yellow for use on 2.
Snapshot 2. For the counterexample, Kempe's chains get tangled at the last step, when vertex 1 is to be colored. One tries to eliminate the green at 12 by switching green and yellow at 12 and 7; thus vertex 7 becomes green. Then the attempted elimination of the other green at 10 via a green/blue chain (10, 9, 7, 6, 13, 8, 11, 5) hits the newly colored green at 7 and continues through to 5, which ends up green, thus foiling the attempt.
Snapshot 3. For this permutation of the bad example the last step again involves vertex 1, but now only three colors appear among its five neighbors so it gets colored green.
For complete details of the Kempe chain operation see [1] or [2]. The method always works when there are four neighbors of the current vertex. While the error in Kempe's method was discovered by P. J. Heawood in 1889, the first example of a graph that foils the algorithm was due to A. Errera in 1921.
While the success probability for permutations of the Errera graph is 90%, for the graph consisting of several disjoint copies of the Errera graph, this probability would quickly decrease. Thus one should use a more general method that combines Kempe's ideas with those of I. Kittell; see details in [2].
[1] J. P. Hutchinson and S. Wagon, "Kempe Revisited," American Mathematical Monthly, 105, (1998) pp. 170–174.
[2] S. Wagon, Mathematica in Action, 3rd ed., New York: Springer-Verlag, 2010.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+