Heawood Conjecture

The bound for the number of colors which are Sufficient for Map Coloring on a surface of Genus $g$,

$$\chi(g)=\left\lfloor{{\textstyle{1\over 2}}(7+\sqrt{48g+1}\,)}\right\rfloor$$

is the best possible, where $\left\lfloor{x}\right\rfloor$ is the Floor Function. $\chi(g)$ is called the Chromatic Number, and the first few values for $g=0$, 1, ... are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, ... (Sloane's A000934).

The fact that $\chi(g)$ is also Necessary was proved by Ringel and Youngs (1968) with two exceptions: the Sphere (Plane), and the Klein Bottle (for which the Heawood Formula gives seven, but the correct bound is six). When the Four-Color Theorem was proved in 1976, the Klein Bottle was left as the only exception. The four most difficult cases to prove were $g=59$, 83, 158, and 257.

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

References

Ringel, G. Map Color Theorem. New York: Springer-Verlag, 1974.

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

Sloane, N. J. A. Sequence A000934/M3292 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Wagon, S. ``Map Coloring on a Torus.'' §7.5 in Mathematica in Action. New York: W. H. Freeman, pp. 232-237, 1991.