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. Youngs bewiesen, dass diese Anzahl auch notwendig ist, mit Ausnahme der orientierbaren Kleinsche Flasche und der Kugel. Für die Kugel wurde daher ein ganz anderer Ansatz gewählt, der zum Beweis des Vier-Farben-Satz geführt hat. Die Kleinsche Flasche blieb eine Ausnahme.

Formale Darstellung

Der Franklin-Graph.

Percy Heawood vermutete 1890, dass für ein gegebenes Geschlecht g > 0 die minimale Anzahl der benötigten Farben für die Färbung aller Graphen auf der Oberfläche einer orientierbaren Mannigfaltigkeit dieses Geschlechts (oder äquivalent dazu die Färbung einer Zerlegung dieser Fläche in einfach zusammenhängende Flächen) gegeben ist durch:

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

wobei $\left \lfloor x \right \rfloor$ die Abrundungsfunktion ist.

Wenn man das Geschlecht durch die Euler-Charakteristik ersetzt, erhält man die Formel, die sowohl orientierbare als auch nicht-orientierbare Fälle abdeckt,

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

Diese Relation funktioniert, wie Ringel und Youngs bewiesen, für alle Flächen, außer für die Kleinsche Flasche. Philip Franklin bewies 1930, dass für die Kleinsche Flasche höchstens 6 Farben benötigt werden, statt 7 wie von der Formel vorhergesagt. Der Franklin-Graph kann in eine Kleinschen Flasche gezeichnet werden, so dass sie sechs gegenseitig berührende Flächsen bildet, so dass diese Grenze scharf ist.

In der einen Richtung ist der Beweis unkompliziert: Durch Manipulation der Euler-Charakteristic kann man zeigen, dass jeder Graph, der in die Oberfläche eingebettet ist, wenigstens einen Knoten des Grades kleiner als die gegebene Schranke hat. Wenn man diesen Knoten entfernt und den restlichen Graphen färbt, dann gewährleistet die kleine Anzahl von Nachbarknoten, dass man den entfernten Knoten dem Graphen wieder hinzufügen kann, ohne die Farbanzahl wieder zu erhöhen. In umgekehrter Richtung ist der Beweis komplizierter und erfordert, dass in jedem Fall (außer der Kleinschen Flasche) ein Vollständiger Graph mit der Anzahl von Knoten gleich der Anzahl der Farben auf der Oberfläche gezeichnet werden kann.

Beispiel

Eine Zerlegung eines Torus in sieben gegenseitig berührende Flächen.

Der Torus hat das Geschlecht g = 1, also χ = 0. Daher kann, wie die Formel vorhersagt, jede Unterteilung des Torus mit höchstens sieben Farben eingefärbt werden. Das Bild zeigt eine Unterteilung des Torus, in der jede der sieben Regionen zu jeder anderen benachbart ist. Dabei muss man jedes Paar gegenüberliegender Seiten des dargestellten Quadrates miteinander identifizieren und so dieses Quadrat zu einem Torus verkleben. Diese Zerlegung zeigt daher, dass die Grenze von sieben Farben in diesem Fall scharf ist. Die Begrenzungen der Unterteilung bilden auf dem Torus einen Heawood-Graphen.

Literatur

• Franklin, P.: A six color problem, J. Math. Phys. 13, 1934, S. 363-379 (englisch)
• Heawood, P. J.: Map colour theorem, Quart. J. Math. 24, 1890, S. 332-338 (englisch)
• Ringel, G.; Youngs, J. W. T.: Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. USA 60, 1968, S. 438-445, doi:10.1073/pnas.60.2.438 (englisch)

Weblinks

• Eric W. Weisstein: Heawood Conjecture. In: MathWorld. (englisch)