mathworld.wolfram.com

Torus Coloring -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

The number of colors sufficient for map coloring on a surface of genus g is given by the Heawood conjecture,

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

where |_x_| 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.

TorusColoring

K7TorusColoring

A g-holed torus therefore requires chi(g) colors. 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 the maximum of seven regions is shown above for a normal 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.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: Penguin, pp. 228-229, 1991.

Referenced on Wolfram|Alpha

Torus Coloring

Cite this as:

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

Subject classifications