Set of Ringel Youngs

The set of curl Youngs also Heawood conjecture called, is in Graph theory , a formula for the minimum number of colors for the color of any area is needed depends on the topological sex of the surface (where a generation here is considered). ${\ displaystyle g> 0}$

Percy Heawood had given the formula in 1890, proved that this formula is an upper bound for gender and formulated the conjecture that it is also a lower bound. In other words, he proved that every map on the corresponding areas can be colored with the number of colors given by the formula, and he assumed that in general it would not be possible to use fewer colors. In 1968 this was proved by Gerhard Ringel and J. W. T. Youngs , with the exception of the cases of the Klein bottle and the ball . The case of the sphere (gender g = 0) corresponds to the difficult case of the four-color theorem ${\ displaystyle g> 0}$ (The problem here is to prove the upper bound, for the lower bound one can give a simple map that can only be colored with four colors) and was only proven in 1977, but the formula is also valid here. The Klein bottle remained an exception for the validity of the formula.

Formal representation

The Franklin graph .

Percy Heawood hypothesized in 1890 that for a given gender g > 0 the minimum number of colors required to color all graphs on the surface of an orientable manifold of this gender (or, equivalently, the coloring of a decomposition of this surface into simply connected surfaces ) is given by :

{\ displaystyle \ gamma (g) = \ left \ lfloor {\ frac {7 + {\ sqrt {1 + 48g}}} {2}} \ right \ rfloor,}

where is the rounding function . ${\ displaystyle \ left \ lfloor x \ right \ rfloor}$

If one replaces the gender with the Euler characteristic , one obtains the formula that covers both orientable and non-orientable cases,

{\ displaystyle \ gamma (\ chi) = \ left \ lfloor {\ frac {7 + {\ sqrt {49-24 \ chi}}} {2}} \ right \ rfloor.}

As Ringel and Youngs proved, this formula works for all surfaces except for the Klein bottle . Philip Franklin proved in 1930 that the Klein bottle needed a maximum of 6 colors instead of 7 as predicted by the formula. The Franklin graph can be drawn in a Klein bottle so that it forms six mutually touching surfaces. So this limit is sharp.

The proof is straightforward in one direction: By manipulating the Euler characteristic one can show that every graph embedded in the surface has at least one node of degree smaller than the given bound. If you remove this node and color the rest of the graph, the small number of neighboring nodes ensures that you can add the removed node to the graph without increasing the number of colors again. In the opposite direction, the proof is more complicated and requires that in each case (except for Klein's bottle) a complete graph can be drawn with the number of nodes equal to the number of colors on the surface.

example

A torus is broken down into seven mutually touching surfaces.

The torus has gender g = 1, i.e. = 0. Therefore, as the formula predicts, each subdivision of the torus can be colored with a maximum of seven colors. The picture shows a subdivision of the torus in which each of the seven regions is adjacent to each other. You have to identify each pair of opposite sides of the square shown and thus glue this square to a torus. This decomposition therefore shows that the boundary of seven colors is sharp in this case. The boundaries of the subdivision form a Heawood graph on the torus . ${\ displaystyle \ chi}$

literature

P. Franklin: A six color problem . In: J. Math. Phys. , 13, 1934, pp. 363–379 (English)
PJ Heawood: Map color theorem . In: Quart. J. Math. , 24, 1890, pp. 332–338 (English)
G. Ringel, JWT Youngs: Solution of the Heawood map-coloring problem . In: Proc. Nat. Acad. Sci. USA , 60, 1968, pp. 438–445, doi: 10.1073 / pnas.60.2.438 (English)

Web links

Eric W. Weisstein : Heawood Conjecture . In: MathWorld (English).

References and comments

↑ See the article Four Color Problem with an illustration of a flat map that requires four colors. Heawood's method for proving the upper bound was not applicable here in the case of plane / sphere.

[1] See the article Four Color Problem with an illustration of a flat map that requires four colors. Heawood's method for proving the upper bound was not applicable here in the case of plane / sphere.