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

is the best possible, where is the Floor Function. is called the Chromatic Number, and the first few values for , 1, ... are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, ... (Sloane's A000934).

The fact that 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 , 83, 158, and 257.

**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.

© 1996-9

1999-05-25