milan golob

contact
links
cv
home

sitemap
drawings
paintings
installations
projects
reviews

 

Map Coloring and Mathematical Games

new


Four-Color Theorem

The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary do not share the same color. This problem is sometimes also called Guthrie's problem after Francis Guthrie, who first conjectured the theorem in 1853. The conjecture was then communicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on the conjecture.

Fallacious proofs were given independently by Kempe (1879) and Tait (1880). Kempe's proof was accepted for a decade until Heawood showed an error using a map with 18 faces. The Heawood conjecture provided a very general assertion for map coloring, showing that in a genus 0 space (including the sphere or plane), four colors suffice. Ringel and Youngs (1968) proved that for genus g>0, the upper bound provided by the Heawood conjecture also give the necessary number of colors, with the exception of the Klein bottle (for which the Heawood formula gives seven, but the correct bound is six).

Six colors can be proven to suffice for the g=0 case, and this number can easily be reduced to five, but reducing the number of colors all the way to four proved very difficult. This result was finally obtained by Appel and Haken (1977), who constructed a computer-assisted proof that four colors were sufficient. However, because part of the proof consisted of an exhaustive analysis of many discrete cases by a computer, some mathematicians do not accept it. However, no flaws have yet been found, so the proof appears valid. A potentially independent proof has recently been constructed by Robertson.

At a December 2004 scientific meeting in France, Georges Gonthier of the Microsoft Research in Cambridge, announced verification the Robertson proof by formulating the problem in the equational logic program Coq and confirming the validity of each of its steps.
John Ferro has recently debunked a number of purported "short" proofs of the four-color theorem.

Martin Gardner (1975) played an April Fool's joke by (incorrectly) claiming that the map of 110 regions illustrated above requires five colors and constitutes a counterexample to the four-color theorem. However, the coloring of Wagon, obtained algorithmically using Mathematica, clearly shows that this map is, in fact, four-colorable.

 

Map Coloring and Mathematical Games

 

 

References:

- Kenneth Appel and Wolfgang Haken; Every Planar Map is Four-Colorable, II: Reducibility, Illinois Journal of Mathematics 21, 1977.

- Kenneth Appel and Wolfgang Haken; Every Planar Map is Four-Colorable, American Mathematical Society, 1989.

- Kenneth Appel, Wolfgang Haken and John Koch; Every Planar Map is Four Colorable. I: Discharging, Illinois Journal of Mathematics 21, 1977.

- George David Birkhoff; The Reducibility of Maps; The American Journal of Mathematics 35, 1913.

- Martin Gardner; Mathematical Games: The Celebrated Four-Color Map Problem of Topology, Scientific American 203, 1960.

- Martin Gardner; The Four-Color Map Theorem, in Martin Gardner's New Mathematical Diversions from Scientific American, New York, 1966.

- Martin Gardner; Mathematical Games: Six Sensational Discoveries that Somehow or Another have Escaped Public Attention, Scientific American 232, 1975.

- Martin Gardner; Mathematical Games: On Tessellating the Plane with Convex Polygons, Scientific American 232, 1975.

- Frank Harary; The Four Color Conjecture, Graph Theory, Reading, Addison-Wesley, 1994.

- Steven Skiena; Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Reading, Addison-Wesley, 1990.

- David Barnette; Map Coloring, Polyhedra, and the Four-Color Problem, Washington, 1983.

- Philip Franklin;The Four Color Problem, New York, 1941.

- Øystein Ore; The Four-Color Problem. New York, 1967.

- Thomas Saaty and Paul Kainen; The Four-Color Problem: Assaults and Conquest, New York, 1986.

- Eric Weisstein; Books about Four-Color Problem.

- David Wells; The Penguin Dictionary of Curious and Interesting Geometry, London: Penguin, 1991.

- Robin Wilson; Four Colors Suffice: How the Map Problem Was Solved, Princeton University Press, 2004.

bibliographies

 
mx