Hajós-Vermutung

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 Kk als topologischen Minor) enthalten muss. In Kurzform: \chi(G) \ge 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 (Uk) 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 (Uk + 1) auch (Uk) impliziert, widerlegte er damit die Vermutung für alle k \ge 7. Die Fälle für k \le 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 Kk zu einem Kk 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 (wie der Name schon sagt) 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

  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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • György Hajós — György Hajós, auch Georg Hajós zitiert, (* 21. Februar 1912 in Budapest; † 17. März 1972 ebenda) war ein ungarischer Mathematiker, der sich vor allem mit Geometrie beschäftigte. Er studierte an der Péter Pázmány Universität (später in Loránd… …   Deutsch Wikipedia

  • Hadwigers Vermutung — Der K4 als Minor eines Graphen, für dessen Färbung k = 4 Farben benötigt werden. In der Graphentheorie stellt die Vermutung von Hadwiger einen Zusammenhang zwischen Färbbarkeit von Graphen und dem Vorkommen vollständiger Minoren her. Ihre Aussage …   Deutsch Wikipedia

  • Gabriel Andrew Dirac — (* 13. März 1925 in Budapest; † 20. Juli 1984 in Arlesheim) war ein ungarisch britischer Mathematiker, der sich mit Graphentheorie beschäftigte. Gabriel Dirac war der Sohn von Eugene Paul Wigners Schwester Margit aus erster Ehe. Als diese 1937… …   Deutsch Wikipedia

  • László Rédei — (auch als Ladislaus Rédei zitiert; * 15. November 1900 in Rákoskeresztúr, jetzt Teil von Budapest[1]; † 21. November 1980 in Budapest) war ein ungarischer Mathematiker, der sich mit Algebra (insbesondere Gruppentheorie und Theorie der… …   Deutsch Wikipedia

  • Burgus Bacharnsdorf — hf a) Burgus Bacharnsdorf b) Burgus St. Lorenz c) Burgus Rossatz Limes Noricum Abschnitt Strecke 1 Datierung (Belegung) a) spätes 4. Jahrhundert; nachantike Nutzung bis ins hohe Mittelalter, b) 4 5 Jahrhundert ?, c) 2. bis spätes 4 …   Deutsch Wikipedia

  • Hadwiger–Nelson-Problem — Das Hadwiger–Nelson Problem ist ein nach Hugo Hadwiger und Edward Nelson benanntes Problem der Geometrischen Graphentheorie. Gesucht wird die minimal benötigte Anzahl an Farben, um eine Ebene derart einzufärben, dass jeweils zwei Punkte mit… …   Deutsch Wikipedia

  • Karl Reinhardt (Mathematiker) — Karl Reinhardt (* 27. Januar 1895 in Frankfurt am Main; † 27. April 1941 in Berlin; vollständiger Name: Karl August Reinhardt) war ein deutscher Mathematiker. Inhaltsverzeichnis 1 Leben und Wirken 2 Schriften 3 Weblinks …   Deutsch Wikipedia

  • Theodor Schmidt (Physiker) — Theodor Schmidt[1] (* 29. Juli 1908 in Düsseldorf; † 10. Dezember 1986 in Sulzburg; vollständiger Name: Karl Theodor Schmidt) war ein deutscher Physiker und Mathematiker. Schmidt studierte nach dem Abitur in Düsseldorf ab 1927 an der Universität… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”