In mathematics, the Heawood number of a

surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is t ...

is an

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...

for the number of colors that suffice to color any

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

embedded in the surface. In 1890 Heawood proved for all surfaces ''except'' the

sphere A sphere () is a geometrical object that is a three-dimensional analogue to a two-dimensional circle. A sphere is the set of points that are all at the same distance from a given point in three-dimensional space.. That given point is the ...

that no more than :

H(S)=\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor

colors are needed to color any graph embedded in a surface of

Euler characteristic In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space' ...

e(S)

, or

genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of living and fossil organisms as well as viruses. In the hierarchy of biological classification, genus comes above species and below family. In binomial nomencla ...

g(S)

for an orientable surface. The number

H(S)

became known as Heawood number in 1976. Klein_bottle_colouring

Franklin proved that the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of a graph embedded in the

Klein bottle In topology, a branch of mathematics, the Klein bottle () is an example of a non-orientable surface; it is a two-dimensional manifold against which a system for determining a normal vector cannot be consistently defined. Informally, it is a ...

can be as large as

6

, but never exceeds

6

. Later it was proved in the works of Gerhard Ringel, J. W. T. Youngs, and other contributors that the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

with

H(S)

vertices can be embedded in the surface

S

unless

S

is the

. This established that Heawood's bound could not be improved. For example, the complete graph on

7

vertices can be embedded in the

torus In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle. If the axis of revolution does not tou ...

as follows: The case of the sphere is the four-color conjecture, which was settled by

Kenneth Appel Kenneth Ira Appel (October 8, 1932 – April 19, 2013) was an American mathematician who in 1976, with colleague Wolfgang Haken at the University of Illinois at Urbana–Champaign, solved one of the most famous problems in mathematics, the four ...

and

Wolfgang Haken Wolfgang Haken (June 21, 1928 – October 2, 2022) was a German American mathematician who specialized in topology, in particular 3-manifolds. Biography Haken was born in Berlin, Germany. His father was Werner Haken, a physicist who had Ma ...

in 1976.

Notes

Béla Bollobás Béla Bollobás FRS (born 3 August 1943) is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory, and percolation. He was strongly influenced by Paul E ...

, ''Graph Theory: An Introductory Course'', Graduate Texts in Mathematics, volume 63, Springer-Verlag, 1979. . *

Thomas L. Saaty Thomas L. Saaty (July 18, 1926 – August 14, 2017) was a Distinguished University Professor at the University of Pittsburgh, where he taught in the Joseph M. Katz Graduate School of Business. He is the inventor, architect, and primary theoretici ...

and

Paul Chester Kainen Paul Chester Kainen is an American mathematician, an adjunct associate professor of mathematics and director of the Lab for Visual Mathematics at Georgetown University. Kainen is the author of a popular book on the four color theorem, and is also ...

; ''The Four-Color Problem: Assaults and Conquest'', Dover, 1986. . {{PlanetMath attribution, id=3876, title=Heawood number

References

Topological graph theory Graph coloring