TOPICS
Search

Torus Coloring

Torus coloring is map coloring on a torus. More generally, for a connected closed surface that is an orientable surface of genus g>=0, the maximum chromatic number over maps with connected regions, where adjacent regions share a boundary arc, is

chi(g)=|_1/2(7+sqrt(48g+1))_|,

where |_x_| is the floor function. For g>=1, sharpness of this bound was proved by Ringel and Youngs (1968, pp. 438-439), resolving the Heawood conjecture. The case g=0 is the four-color theorem. The Klein bottle is nonorientable and is outside this family.

TorusColoring
K7TorusColoring

A g-holed torus therefore has worst-case map chromatic number chi(g). For g=0, 1, ..., the first few values of chi(g) are 4, 7 (illustrated above, M. Malak, pers. comm., Feb. 22, 2006), 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, ... (OEIS A000934). A set of regions requiring seven colors is shown above for an ordinary torus.

HeawoodTorusColoring

The above figure shows the relationship between the Heawood graph and the 7-color torus coloring.

See also

Chromatic Number, Four-Color Theorem, Heawood Conjecture, Heawood Graph, Klein Bottle, Map Coloring, Szilassi Polyhedron, Torus

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 244, 1976.Cadwell, J. H. Ch. 8 in Topics in Recreational Mathematics. Cambridge, England: Cambridge University Press, 1966.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. https://doi.org/10.1073/pnas.60.2.438.Sloane, N. J. A. Sequence A000934/M3292 in "The On-Line Encyclopedia of Integer Sequences."Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 274-275, 1999.Wagon, S. "Map Coloring on a Torus." §7.5 in Mathematica in Action. New York: W. H. Freeman, pp. 232-237, 1991.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 70, 1986.Wells, D. The Penguin Dictionary of Curious and Interesting Geometry. London, England: Penguin, pp. 228-229, 1991.

Referenced on Wolfram|Alpha

Torus Coloring

Cite this as:

Weisstein, Eric W. "Torus Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TorusColoring.html

Subject classifications