mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, 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 every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

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

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

sphere A sphere (from Ancient Greek, Greek , ) is a surface (mathematics), surface analogous to the circle, a curve. In solid geometry, 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's ...

e(S)

, or

genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...

g(S)

for an orientable surface. The number

H(S)

became known as the Heawood number in 1976. Klein_bottle_colouring

Franklin proved that the

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

of a graph embedded in the

Klein bottle In mathematics, the Klein bottle () is an example of a Orientability, non-orientable Surface (topology), surface; that is, informally, a one-sided surface which, if traveled upon, could be followed back to the point of origin while flipping the ...

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

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 (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanarity, coplanar with the circle. The main types of toruses inclu ...

as follows: The case of the sphere is the four-color conjecture, which was settled by Kenneth Appel and Wolfgang Haken in 1976.

Notes

* Béla Bollobás, ''Graph Theory: An Introductory Course'', Graduate Texts in Mathematics, volume 63, Springer-Verlag, 1979. . * Thomas L. Saaty and Paul Chester Kainen; ''The Four-Color Problem: Assaults and Conquest'', Dover, 1986. . {{PlanetMath attribution, id=3876, title=Heawood number

References

Topological graph theory Graph coloring