The number of colors Sufficient for Map Coloring on a surface of Genus is
given by the Heawood Conjecture,

where is the Floor Function. The fact that (which is called the Chromatic Number) is also Necessary was proved by Ringel and Youngs (1968) with two exceptions: the Sphere (which requires the same number of colors as the Plane) and the Klein Bottle. A -holed Torus therefore requires colors. For , 1, ..., the first few values of are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, ... (Sloane's A000934).

**References**

Gardner, M. ``Mathematical Games: The Celebrated Four-Color Map Problem of Topology.'' *Sci. Amer.* **203**, 218-222, Sep. 1960.

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-26