Heawood number

{{Short description|Upper bound for number of colors that suffice to color any graph}}

File:Taxel genus 3 colouring.svg

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

:$H(S)=\backslash left\backslash lfloor\backslash frac\{7+\backslash sqrt\{49-24\; e(S)\}\}\{2\}\backslash right\backslash rfloor\; =\; \backslash left\backslash lfloor\backslash frac\{7+\backslash sqrt\{1+48\; g(S)\}\}\{2\}\backslash right\backslash rfloor$

colors are needed to color any graph embedded in a surface of Euler characteristic $e(S)$, or genus $g(S)$ for an orientable surface.{{citation | author=P. J. Heawood | authorlink=Percy John Heawood | title=Map colouring theorems | journal = Quarterly J. Math. | year=1890 | volume=24 | pages=322–339}}

The number $H(S)$ became known as the Heawood number in 1976.

File:Klein_bottle_colouring.svg]]

Franklin proved that the chromatic number of a graph embedded in the Klein bottle can be as large as $6$, but never exceeds $6$.{{Citation | author=P. Franklin |year=1934 |title=A six color problem |journal=Journal of Mathematics and Physics |volume=13|issue=1–4 |pages=363–379|doi=10.1002/sapm1934131363 }} Later it was proved in the works of Gerhard Ringel, J. W. T. Youngs, and other contributors that the complete graph with $H(S)$ vertices can be embedded in the surface $S$ unless $S$ is the Klein bottle.{{Citation|author=Gerhard Ringel | author2=J. W. T. Youngs| title =Solution of the Heawood Map-Coloring Problem|volume = 60|number = 2|pages = 438–445|year = 1968|doi = 10.1073/pnas.60.2.438|issn = 0027-8424|journal = Proceedings of the National Academy of Sciences|pmc = 225066| pmid = 16591648| bibcode=1968PNAS...60..438R| doi-access=free}} This established that Heawood's bound could not be improved.

For example, the complete graph on $7$ vertices can be embedded in the torus as follows:

350px

The case of the sphere is the four-color conjecture, which was settled by Kenneth Appel and Wolfgang Haken in 1976.{{Citation |author=Kenneth Appel |author2=Wolfgang Haken |year=1977 |title=Every Planar Map is Four Colorable. I. Discharging |journal=Illinois Journal of Mathematics| volume=21 |pages=429–490| issue=3 | mr=0543792 | url=http://projecteuclid.org/euclid.ijm/1256049011}}{{Citation |author=Kenneth Appel |author2=Wolfgang Haken |author3=John Koch |year=1977 |title=Every Planar Map is Four Colorable. II. Reducibility |journal=Illinois Journal of Mathematics| volume=21 |pages=491–567| mr=0543793 | issue=3 | url=http://projecteuclid.org/euclid.ijm/1256049012 | doi=10.1215/ijm/1256049012|doi-access=free }}