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 formula_2, or genus formula_3 for an orientable surface. The number formula_4 became known as Heawood number in 1976. Franklin proved that the chromatic number of a graph embedded in the Klein bottle can be as large as formula_5, but never exceeds formula_5. Later  it was proved in the works of Gerhard Ringel, J. W. T. Youngs, and other contributors that the complete graph with formula_4 vertices can be embedded in the surface formula_8 unless formula_8 is the Klein bottle. This established that Heawood's bound could not be improved. For example, the complete graph on formula_10 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.