Heawood number

The Heawood number of a surface is an upper bound for the maximal number of colors needed 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 characteristicMathworldPlanetmath e(S). The case of the sphere is the four-color conjecture which was settled by Appel and Haken in 1976. The number H(S) became known as Heawood number in 1976. Franklin proved that the chromatic numberMathworldPlanetmath of a graph embedded in the Klein bottleMathworldPlanetmath can be as large as 6, but never exceeds 6. Later it was proved in the works of Ringel and Youngs that the complete graphMathworldPlanetmath of H(S) vertices can be embedded in the surface S unless S is the Klein bottle. This established that Heawood’s bound could not be improved.

For example, the complete graph on 7 vertices can be embedded in the torus as follows:



  • 1 Béla Bollobás. Graph TheoryMathworldPlanetmath: An Introductory Course, volume 63 of GTM. Springer-Verlag, 1979. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0411.05032Zbl 0411.05032.
  • 2 Thomas L. Saaty and Paul C. Kainen. The Four-Color Problem: Assaults and Conquest. Dover, 1986. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0463.05041Zbl 0463.05041.
Title Heawood number
Canonical name HeawoodNumber
Date of creation 2013-03-22 13:21:21
Last modified on 2013-03-22 13:21:21
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 12
Author bbukh (348)
Entry type Theorem
Classification msc 05C15
Classification msc 05C10
Related topic FourColorConjecture