is the best possible, where is the floor function.
is called the chromatic number, and the first
few values for ,
1, ... are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, ... (OEIS A000934).
The fact that
is also necessary was proved by Ringel and Youngs (1968)
with two exceptions: the sphere (and plane),
and the Klein bottle. When the four-color
theorem was proved in 1976, the Klein bottle
was left as the only exception, in that the Heawood formula gives seven, but the
correct bound is six (as demonstrated by the Franklin
graph). The four most difficult cases to prove in the Heawood conjecture 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-379, 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 the floor function.
is called the chromatic number, and the first
few values for 
,
1, ... are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, ... (OEIS A000934).
is also necessary was proved by Ringel and Youngs (1968)
with two exceptions: the sphere (and plane),
and the Klein bottle. When the four-color
theorem was proved in 1976, the Klein bottle
was left as the only exception, in that the Heawood formula gives seven, but the
correct bound is six (as demonstrated by the Franklin
graph). The four most difficult cases to prove in the Heawood conjecture were
,
83, 158, and 257.
