Torus Coloring

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

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

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength