Heawood conjecture


Heawood conjecture

The Heawood conjecture or Ringel–Youngs theorem in graph theory gives an upper bound for the number of colors which are sufficient for graph coloring on a surface of a given genus. It was proven in 1968 by Gerhard Ringel and J. W. T. Youngs. One case, the non-orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for finding the number of colors needed for the sphere, eventually solved as the four color theorem.

Formal statement

P.J. Heawood conjectured in 1890 that for a given genus "g" > 0, the minimum number of colors necessary to color all graphs drawn on an orientable surface of that genus (or equivalently to color the regions of any partition of the surface into simply connected regions) is given by

:gamma (g) = left lfloor frac{7 + sqrt{1 + 48g{2} ight floor,

where left lfloor x ight floor is the floor function.

Replacing the genus by the Euler characteristic, we obtain a formula that covers both the orientable and non-orientable cases,

: gamma(chi) = left lfloor frac{7 + sqrt{49 - 24chi2 ight floor.

This relation holds, as Ringel and Youngs showed, for all surfaces except for the Klein bottle. Franklin (1930) proved that the Klein bottle requires at most 6 colors, rather than 7 as predicted by the formula (see Franklin graph).

In one direction, the proof is straightforward: by manipulating the Euler characteristic, one can show that any graph embedded in the surface must have at least one vertex of degree less than the given bound. If one removes this vertex, and colors the rest of the graph, the small number of edges incident to the removed vertex ensures that it can be added back to the graph and colored without increasing the needed number of colors beyond the bound. In the other direction, the proof is more difficult, and involves showing that in each case (except the Klein bottle) a complete graph with a number of vertices equal to the given number of colors can be embedded on the surface.

Example

The torus has "g" = 1, so χ = 0. Therefore, as the formula states, any subdivision of the torus into regions can be colored using at most seven colors. The illustration shows a subdivision of the torus in which each of seven regions are adjacent to each other region; this subdivision shows that the bound of seven on the number of colors is tight for this case. The boundary of this subdivision forms an embedding of the Heawood graph onto the torus.

References

*cite journal
author = Franklin, P.
title = A six color problem
journal = J. Math. Phys.
volume = 13
pages = 363–379
year = 1934

*cite journal
author = Heawood, P. J.
title = Map colour theorem
journal = Quart. J. Math.
volume = 24
pages = 332–338
year = 1890

*cite journal
author = Ringel, G.; Youngs, J. W. T.
title = Solution of the Heawood map-coloring problem
journal = Proc. Nat. Acad. Sci. USA
volume = 60
pages = 438–445
year = 1968
id = MathSciNet | id = 0228378
doi = 10.1073/pnas.60.2.438

External links

*mathworld | urlname = HeawoodConjecture | title = Heawood Conjecture


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Heawood number — In mathematics, the Heawood number of a surface is a certain upper bound for the maximal number of colors needed to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces except the sphere that no more than:… …   Wikipedia

  • Percy John Heawood — Percy Heawood Born September 8, 1861(1861 09 08) Newport, Shropshire, England Died January 24, 1955(1955 01 …   Wikipedia

  • Percy John Heawood — Naissance 8 septembre 1861 Newport, Shropshire (Angleterre) Décès 24 janvier 1955 (à 93 ans) Durham (Angleterre) Domicile Royaume Uni Nationalité …   Wikipédia en Français

  • Four color theorem — Example of a four colored map A four colori …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

  • Satz von Ringel-Youngs — Die Satz von Ringel Youngs, auch Heawood Vermutung genannt, gibt in der Graphentheorie eine obere Schranke für die Anzahl der Farben, die für die Färbung einer Fläche eines Geschlechts hinreichend ist. 1968 wurde von Gerhard Ringel und J. W. T.… …   Deutsch Wikipedia

  • Gerhard Ringel — surfant Pour les articles homonymes, voir Ringel (homonymie). Gerhard Ringel (28 octobre 1919, à Kollnbrunn (Autriche …   Wikipédia en Français

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • Liste Des Conjectures Mathématiques — Ce qui suit est une liste de conjectures mathématiques, contenues dans les pages de Wikipedia. Elles sont divisées en quatre sections, en accord avec leur état en 2006. Voir aussi : La conjecture d Erdős, qui liste les conjectures de Paul… …   Wikipédia en Français