Heawood conjecture

The Heawood conjecture gives the maximum chromatic number of graphs embeddable on a surface of genus g as ⌊(7 + √(1 + 48g))/2⌋, except on the Klein bottle.

Graph coloring: An assignment of colors to graph vertices in which adjacent vertices receive different colors. The conjecture bounds the colors required for graphs constrained by a surface.
Percy John Heawood: An English mathematician who studied map coloring and formulated the genus-dependent bound now bearing his name. His 1890 work proposed the formula for surfaces beyond the sphere.
Klein bottle: A closed, nonorientable surface with no global distinction between clockwise and counterclockwise orientation. Its maximum graph chromatic number is six, unlike the formula's value of seven.
Topological graph theory: The study of graphs drawn on surfaces and the topological properties of those drawings. The conjecture is a central extremal result in this field.
Chromatic number: The least number of colors needed to color a graph so that adjacent vertices have different colors. It is the graph quantity maximized in the conjecture.
Francis Guthrie: A South African mathematician known for posing the four-color problem in 1852. The map-coloring problem he raised inspired the broader surface-coloring question.
Four-color theorem: Every planar map can be colored with at most four colors so neighboring regions differ. For genus zero, the conjectured expression overshoots the true planar maximum.
Heawood graph: A 14-vertex, 21-edge graph embedded on the torus with chromatic number seven. It is a compact example attaining the bound for genus one.
Graph embedding: A drawing of a graph on a surface in which vertices are distinct points and edges meet only at shared endpoints. Embeddability on a surface determines which graphs enter the bound.
Gerhard Ringel: A German mathematician who helped establish the chromatic numbers of surfaces through topological graph theory. His work supplied major parts of the proof for higher-genus surfaces.

Linked from 1 page