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.
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 244, 1976.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.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.
