mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 ...

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 element ...

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 discre ...

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

sphere A sphere () is a Geometry, geometrical object that is a solid geometry, three-dimensional analogue to a two-dimensional circle. A sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...

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 extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...

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 o ...

can be as large as

6

, but never exceeds

6

. Later it was proved in the works of

Gerhard Ringel Gerhard Ringel (October 28, 1919 in Kollnbrunn, Austria – June 24, 2008 in Santa Cruz, California) was a German mathematician. He was one of the pioneers in graph theory and contributed significantly to the proof of the Heawood conjecture (now ...

, 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 c ...

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 In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...

, 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-c ...

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 Max ...

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 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