Torus Coloring

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

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

where $\left\lfloor{x}\right\rfloor$ is the Floor Function. The fact that $\chi(g)$ (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 $g$-holed Torus therefore requires $\chi(g)$ colors. For $g=0$, 1, ..., the first few values of $\chi(g)$ are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, ... (Sloane's A000934).

See also Chromatic Number, Four-Color Theorem, Heawood Conjecture, Klein Bottle, Map Coloring

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.