Hadwigers Vermutung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der K_4 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 ist, dass ein Graph, der keine gültige Färbung mit weniger als k Farben besitzt, einen K_k-Minor hat. In Kurzform: \chi(G) \ge k \ \Rightarrow \ K_k \preceq G. Als Abkürzung wird häufig die Bezeichnung (H_k) verwendet.

Die Vermutung verallgemeinert den Vier-Farben-Satz, der zusammen mit dem Satz von Kuratowski die Aussage für k=5 impliziert. Ebenfalls für k=6 basiert der bisher einzige Beweis auf der Annahme der Gültigkeit des Vier-Farben-Satzes. Die Vermutung wurde 1943 von Hugo Hadwiger aufgestellt und ist ein offenes Problem der Mathematik. Béla Bollobás, Paul Allen Catlin und Paul Erdős (1980) nannten es „eines der tiefliegendsten ungelösten Probleme der Graphentheorie“.[1]

Die Vermutung verschärft die Folgerung aus dem 2004 bewiesenen Satz von Robertson-Seymour, dass die Klasse F_k der Graphen, deren Minoren alle k-1-färbbar sind, durch eine endliche Menge verbotener Minoren charakterisiert ist. Hadwigers Vermutung besagt, dass diese Menge nur den K_k-Minor enthält. Neil Robertson, Paul Seymour und Robin Thomas konnten 1993 Hadwigers Vermutung für k\le 6 beweisen.[2]

Als Verschärfung der Vermutung von Hadwiger gilt die Hajós-Vermutung, die den K_k nicht als Minor, sondern sogar als topologischen Minor fordert. Diese Vermutung ist für k \le 5 korrekt, für k=6 offen und für alle größeren k falsch, was jedoch keine Auswirkungen auf die Vermutung von Hadwiger hat.

Stand der Dinge[Bearbeiten]

Die Vermutung von Hadwiger ist – wie gesagt – noch nicht vollständig bewiesen. Für die Fälle k \le 4 ist sie leicht zu zeigen. Für den Fall k=5 ist es schon etwas anspruchsvoller und für k=6 ist der Beweis bereits recht lang.

Es ist klar, dass die Vermutung entweder für alle k korrekt ist, oder aber ein größtes k' existiert, sodass sie für alle k \le k' korrekt und alle k > k' falsch ist.

Für alle k \ge 5 impliziert die Vermutung den Vier-Farben-Satz.

1980 zeigten Bela Bollobas, Paul Catlin und Paul Erdős mit der probabilistischen Methode, dass die Vermutung für fast alle Graphen korrekt ist.[3]

2009 konnten Maria Chudnovsky und Alexandra Ovetsky Fradkin zeigen, dass die Hadwiger-Vermutung für die Klasse der Klauen-freien Graphen korrekt ist,[4] womit sie das Ergebnis von Seymour, Robertsen und Thomas, dass die Vermutung für alle Kantengraphen korrekt ist, ausweiteten.

Dominic van der Zypen konstruierte 2012 einen Graphen H mit chromatischer Zahl ω, aber ohne unendlichen vollständigen Minor. Das zeigt, dass Hadwigers Vermutung im Abzählbar-Unendlichen nicht gilt.[5]

Einzelnachweise[Bearbeiten]

  1. B. Bollobás, P. Catlin und P. Erdős: Hadwiger's conjecture is true for almost every graph. (1980) in: European Journal on Combinatorics. 1: 195–199.
  2. N. Robertson, P. Seymour, R. Thomas: Hadwiger's conjecture for K_6-free graphs. (1993) in: Combinatorica. 13: 279–361 doi: 10.1007/BF01202354.
  3. B. Bollobas, P. A. Catlin, P. Erdős: Hadwiger's Conjecture is true for Almost Every Graph. (PDF; 205 kB).
  4. M. Chudnowski, A. O. Fradkin: An Approximate Version of Hadwiger's Conjecture for Claw-Free Graphs.
  5. Dominic van der Zypen: Hadwiger’s conjecture for graphs with infinite chromatic number. 2012.