Map Coloring

Given a map with Genus $g>0$, Heawood showed in 1890 that the maximum number $N_u$ of colors necessary to color a map (the Chromatic Number) on an unbounded surface is

$$N_u\equiv \left\lfloor{{\textstyle{1\over 2}}(7+\sqrt{48g+1}... ...r{{\textstyle{1\over 2}}(7+\sqrt{49-24\chi}\,)}\right\rfloor ,$$

where $\left\lfloor{x}\right\rfloor$ is the Floor Function, $g$ is the Genus, and $\chi$ is the Euler Characteristic. This is the Heawood Conjecture. In 1968, for any orientable surface other than the Sphere (or equivalently, the Plane) and any nonorientable surface other than the Klein Bottle, $N_u$ was shown to be not merely a maximum, but the actual number needed (Ringel and Youngs 1968).

When the Four-Color Theorem was proven, the Heawood Formula was shown to hold also for all orientable and nonorientable surfaces with the exception of the Klein Bottle. For this case, the actual number of colors $N$ needed is six--one less than $N_u=7$ (Franklin 1934; Saaty 1986, p. 45).

surface	$g$	$N_u$	$N$
Klein Bottle	1	7	6
Möbius Strip	${\textstyle{1\over 2}}$	6	6
Plane	0	4	4
Projective Plane	${\textstyle{1\over 2}}$	6	6
Sphere	0	4	4
Torus	1	7	7

See also Chromatic Number, Four-Color Theorem, Heawood Conjecture, Six-Color Theorem, Torus Coloring

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 237-238, 1987.

Barnette, D. Map Coloring, Polyhedra, and the Four-Color Problem. Washington, DC: Math. Assoc. Amer., 1983.

Franklin, P. ``A Six Colour Problem.'' J. Math. Phys. 13, 363-369, 1934.

Franklin, P. The Four-Color Problem. New York: Scripta Mathematica, Yeshiva College, 1941.

Ore, Ø. The Four-Color Problem. New York: Academic Press, 1967.

Ringel, G. and Youngs, J. W. T. ``Solution of the Heawood Map-Coloring Problem.'' Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.

Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, 1986.