Hajós-Vermutung

Die Vermutung von Hajós ist eine Vermutung aus der Graphentheorie. Sie wurde in den 1950er Jahren vom Mathematiker György Hajós aufgestellt[1] und besagt, dass ein Graph, der nicht mit weniger als ${\displaystyle k}$ Farben gefärbt werden kann, eine Unterteilung des vollständigen Graphen auf ${\displaystyle k}$ Ecken (d. h. den ${\displaystyle K_{k}}$ als topologischen Minor) enthalten muss. In Kurzform: ${\displaystyle \chi (G)\geq k\ \Rightarrow \ K_{k}\preceq _{T}G}$. Grob gesagt bedeutet das, dass ein Graph, der eine bestimmte chromatische Zahl hat, eine gewisse Struktur beinhalten muss. Als Abkürzung für die Vermutung wird häufig die Bezeichnung ${\displaystyle (U_{k})}$ verwendet.

Lange Zeit wurde vermutet, dass die Vermutung für alle ${\displaystyle k}$ korrekt sei. 1979 veröffentlichte Paul Catlin[2] jedoch eine Arbeit, in der er ein Gegenbeispiel für ${\displaystyle k=7}$ konstruierte. Da jedoch ${\displaystyle (U_{k+1})}$ auch ${\displaystyle (U_{k})}$ impliziert, widerlegte er damit die Vermutung für alle ${\displaystyle k\geq 7}$. Die Fälle für ${\displaystyle k\leq 4}$ sind jedoch korrekt.[3] Der Fall ${\displaystyle k=6}$ ist bis heute noch offen.

Weitere Gegenbeispiele n​ach Catlin f​and Carsten Thomassen[4]. Thomassen f​and aber auch, d​ass lokal planare Graphen u​nd Triangulationen d​er projektiven Ebene u​nd des Torus d​ie Vermutung erfüllen. Bojan Mohar[5] widerlegte a​ber seine weitergehende Vermutung, d​ass alle Triangulationen d​ie Vermutung erfüllen.

Paul Erdős u​nd Fajtlowicz bewiesen 1981 i​m Rahmen d​er probabilistischen Graphentheorie, d​ass die Vermutung für fast alle Graphen falsch ist.[6]

Die Vermutung von Hajós stellt eine Verschärfung der Hadwiger-Vermutung dar, da jeder topologische Minor der ${\displaystyle K_{k}}$ zu einem ${\displaystyle K_{k}}$ kontrahiert werden kann und somit auch ein Minor ist. Es gilt jedoch nicht, dass jeder Minor auch ein topologischer Minor ist. Obwohl sie auf den ersten Blick äquivalent wirken, unterscheiden sich die beiden Vermutungen grundlegend. Bei der Vermutung von Hadwiger geht es um Minoren, welche von der Zeichnung des Graphen eher unabhängig sind und eine kombinatorische Betrachtungsweise erwirken. Bei topologischen Minoren, wie sie in der Vermutung von Hajós gefordert werden, handelt es sich um eine topologische Betrachtungsweise, d. h., dass die Zeichnung des Graphen im Vordergrund steht.

Es g​ibt noch e​ine weitere (im Allgemeinen bisher ungelöste) Hajós-Vermutung über d​ie Kreiszerlegung v​on Graphen.

Einzelnachweise

1. Hajos Über eine Konstruktion nicht n-färbbarer Graphen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe., Bd. 10, 1961, S. 116–117.
2. P. A. Catlin Hajos Graph Coloring Conjecture: Variations and Counterexamples, J. Combinatorial Theory B, Bd. 26, 1979, S. 268–274
3. Für k kleiner oder gleich 4 wurde das von Gabriel Dirac 1952 bewiesen. Dirac A property of 4-chromatic graphs and some remarks on critical graphs, J. London Mathematical Society, Bd. 27, 1952, S. 85–92
4. Thomassen Some remarks on Hajos Conjecture, Journal of Combinatorial Theory B, Bd. 93, 2005, S. 95
5. Mohar Triangulations and the Hajos Conjecture, PDF-Datei
6. Paul Erdős, Simion Fajtlowicz On the conjecture of Hajos, Combinatorica Bd. 1, 1981, S. 141