four-color conjecture


The four-color conjecture was a long-standing problem posed by Francis Guthrie to his professor Augustus De Morgan in 1852, while coloringMathworldPlanetmath a map of England. The conjecture states that every map on a plane or a sphere can be colored using only four colors such that no two adjacent countries are assigned the same color. There are maps that need four colors to be colored as the figure below shows. This conjecture equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to the statement that chromatic numberMathworldPlanetmath of every planar graphMathworldPlanetmath is no more than four.

\scale1 1\gsave\code0 0.5 0 setrgbcolor newpath 180 100 moveto 100 100 80 0 360 arc 150 100 moveto 100 100 50 360 0 arcn fill 1 0 0 setrgbcolor newpath 100 100 moveto 150 100 lineto 100 100 50 0 120 arc closepath fill 0 0 1 setrgbcolor newpath 100 100 moveto 120 cos 50 mul 120 sin 50 mul rlineto 100 100 50 120 240 arc closepath fill 1 1 0 setrgbcolor newpath 100 100 moveto 240 cos 50 mul 240 sin 50 mul rlineto 100 100 50 240 360 arc closepath fill \grestore
Figure 1: Four mutually adjacent countries

After many unsuccessful attempts the conjecture was proven by Appel and Haken in 1976 with the aid of a computer. Before it was known that every planar map can be five-colored by the work of Heawood in 1890.

Interestingly, the seemingly harder problem of determining the maximal number of colors needed for all surfaces other than the sphere was solved long before the four-color conjecture was settled. This is the Heawood number of the surface unless the surface is the Klein bottle in which case it is 6.

References

  • 1 Kenneth O. May. The origin of the four-color conjecture. Isis, 56(3):346–348, 1965. http://links.jstor.org/sici?sici=0021-1753%28196523%2956%3A3%3C346%3ATOOTFC%3E2.0.CO%3B2-ZAvailable online at http://www.jstor.orgJSTOR.
  • 2 Thomas L. Saaty and Paul C. Kainen. The Four-Color Problem: Assaults and Conquest. Dover, 1986. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0463.05041Zbl 0463.05041.
Title four-color conjecture
Canonical name FourcolorConjecture
Date of creation 2013-03-22 13:21:18
Last modified on 2013-03-22 13:21:18
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 19
Author bbukh (348)
Entry type Theorem
Classification msc 05C10
Classification msc 05C15
Synonym Appel-Haken theorem
Synonym 4-color conjecture
Related topic PlanarGraph
Related topic ChromaticNumber
Related topic HeawoodNumber