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 $k$ Farben gefärbt werden kann, eine Unterteilung des vollständigen Graphen auf $k$ Ecken (d. h. den $K_{k}$ als topologischen Minor) enthalten muss. In Kurzform: $\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 $(U_{k})$ verwendet.

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

Weitere Gegenbeispiele nach Catlin fand Carsten Thomassen^[4]. Thomassen fand aber auch, dass lokal planare Graphen und Triangulationen der projektiven Ebene und des Torus die Vermutung erfüllen. Bojan Mohar^[5] widerlegte aber seine weitergehende Vermutung, dass alle Triangulationen die Vermutung erfüllen.

Paul Erdős und Fajtlowicz bewiesen 1981 im Rahmen der probabilistischen Graphentheorie, dass 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 $K_{k}$ zu einem $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 gibt noch eine weitere (im Allgemeinen bisher ungelöste) Hajós-Vermutung über die Kreiszerlegung von Graphen.

Einzelnachweise

↑ 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.
↑ P. A. Catlin Hajos Graph Coloring Conjecture: Variations and Counterexamples, J. Combinatorial Theory B, Bd. 26, 1979, S. 268–274
↑ 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
↑ Thomassen Some remarks on Hajos Conjecture, Journal of Combinatorial Theory B, Bd. 93, 2005, S. 95
↑ Mohar Triangulations and the Hajos Conjecture, PDF-Datei
↑ Paul Erdős, Simion Fajtlowicz On the conjecture of Hajos, Combinatorica Bd. 1, 1981, S. 141

[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

[1]

[2]

[3]

[4]

[5]

[6]