The Heawood conjecture states that the least number of colors sufficient for map coloring on a connected closed orientable surface
of genus is
where
is the floor function. This is the surface chromatic
number. Ringel and Youngs (1968) proved the conjecture. For , the same formula gives 4, whose sufficiency is the
four-color theorem. The values for , 1, ... are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14,
... (OEIS A000934).
For a nonorientable surface of nonorientable genus, the Heawood bound is instead
The Klein bottle has . This formula gives seven colors, but its chromatic
number is six (Franklin 1934). Franklin's six-face map shows that six colors
are necessary. The four most difficult orientable cases to prove were , 83, 158, and 257 (Coxeter 1969, p. 395).
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 244, 1976.Coxeter,
H. S. M. Introduction
to Geometry, 2nd ed. New York: Wiley, p. 395, 1969.Franklin,
P. "A Six Color Problem." J. Math. Phys.13, 363-369, 1934.Heawood,
P. J. "Map Colour Theorem." Quart. J. Math.24, 332-338,
1890.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. USA60, 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."Wagon,
S. "Map Coloring on a Torus." §7.5 in Mathematica
in Action. New York: W. H. Freeman, pp. 232-237, 1991.
is
is the floor function. This is the surface chromatic
number. Ringel and Youngs (1968) proved the conjecture. For 
, the same formula gives 4, whose sufficiency is the
four-color theorem. The values for 
, 1, ... are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14,
... (OEIS A000934).
, the Heawood bound is instead
. This formula gives seven colors, but its chromatic
number is six (Franklin 1934). Franklin's six-face map shows that six colors
are necessary. The four most difficult orientable cases to prove were 
, 83, 158, and 257 (Coxeter 1969, p. 395).
