Heawood conjecture

From Wikipedia, the free encyclopedia

The Heawood conjecture 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.

1 Formal statement
2 Example
3 References
4 External links

[edit] 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} \right \rfloor,$

where $\left \lfloor x \right \rfloor$ 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 - 24\chi}}2 \right \rfloor.$

This relation holds, as Ringel and Youngs showed, for all surfaces except for the Klein bottle. Franklin (1930) proved that the Klein bottle requires 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.

[edit] Example

A partition of the torus into seven mutually adjacent regions, requiring seven colors.

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.