Heawood number

In mathematics, the Heawood number of a surface is an upper bound for the number of colors that suffice to color any graph embedded in the surface.

A 9-coloured triple torus (genus-3 surface) – dotted lines represent handles

In 1890 Heawood proved for all surfaces except the sphere that no more than

${\displaystyle H(S)=\left\lfloor {\frac {7+{\sqrt {49-24e(S)}}}{2}}\right\rfloor =\left\lfloor {\frac {7+{\sqrt {1+48g(S)}}}{2}}\right\rfloor }$

colors are needed to color any graph embedded in a surface of Euler characteristic ${\displaystyle e(S)}$, or genus ${\displaystyle g(S)}$ for an orientable surface.^[1] The number ${\displaystyle H(S)}$ became known as the Heawood number in 1976.

A 6-colored Klein bottle, the only exception to the Heawood conjecture

Franklin proved that the chromatic number of a graph embedded in the Klein bottle can be as large as ${\displaystyle 6}$, but never exceeds ${\displaystyle 6}$.^[2] Later it was proved in the works of Gerhard Ringel, J. W. T. Youngs, and other contributors that the complete graph with ${\displaystyle H(S)}$ vertices can be embedded in the surface ${\displaystyle S}$ unless ${\displaystyle S}$ is the Klein bottle.^[3] This established that Heawood's bound could not be improved.

For example, the complete graph on ${\displaystyle 7}$ vertices can be embedded in the torus as follows:

The case of the sphere is the four-color conjecture, which was settled by Kenneth Appel and Wolfgang Haken in 1976.^[4][5]

Notes

• Béla Bollobás, Graph Theory: An Introductory Course, Graduate Texts in Mathematics, volume 63, Springer-Verlag, 1979. Zbl 0411.05032.
• Thomas L. Saaty and Paul Chester Kainen; The Four-Color Problem: Assaults and Conquest, Dover, 1986. Zbl 0463.05041.

This article incorporates material from Heawood number on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.