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.

In 1890 Heawood proved for all surfaces except the sphere that no more than colors are needed to color any graph embedded in a surface of Euler characteristic

Franklin proved that the chromatic number of a graph embedded in the Klein bottle can be as large as

[2] Later it was proved in the works of Gerhard Ringel, J. W. T. Youngs, and other contributors that the complete graph with

[3] This established that Heawood's bound could not be improved.

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

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