Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung.

Satz

Die endlichen Graphen sind durch die Minorenrelation wohlquasigeordnet.

So simpel dieser Satz anmutet, so komplex ist sein Beweis. Mit einigen Lemmata lässt sich aus dem Minorensatz die Wagnersche Vermutung folgern.

Wagnersche Vermutung (Satz von Robertson-Seymour)

Jede unendliche abzählbare Menge von endlichen Graphen, die abgeschlossen bzgl. der Bildung von Minoren ist (d. h., alle Minoren von Graphen in sollen ebenfalls zu gehören) lässt sich durch eine endliche Menge „verbotener Minoren“ definieren, d. h., es gibt eine endliche Menge endlicher Graphen, so dass übereinstimmt mit der Menge aller endlichen Graphen, die keinen Graphen aus als Minor enthalten.

Beispiel

Ein Beispiel ist die Menge aller in die Ebene einbettbaren Graphen (also der planaren Graphen). Die planaren Graphen sind abgeschlossen bezüglich Minorenbildung, also gibt es eine endliche Menge von verbotenen Minoren, durch die sich alle planaren Graphen charakterisieren lassen. In diesem Fall ist nach dem Satz von Kuratowski .

Auch für jede andere Fläche ist die Menge der in einbettbaren Graphen abgeschlossen bzgl. der Bildung von Minoren, es gibt also eine endliche Menge von „verbotenen Minoren“, die alle in einbettbare Graphen charakterisieren.

Die einzige Fläche , außer Ebene und Sphäre, für welche man die Menge bisher explizit bestimmen konnte, ist die projektive Ebene. Hier besteht aus 103 verbotenen Minoren.

Literatur

Einzelnachweise

  1. ↑ Robertson, Seymour: Graph Minors. I. Excluding a Forest, Journal of Combinatorial Theory B, Band 35, 1983, S. 39–61
  2. ↑ Graph Minors. XX. Wagner's Conjecture, Journal of Combinatorial Theory B, Band 92, 2004, S. 325–357
  3. ↑ Graph Minors. XXIII. Nash-Williams' immersion conjecture, Journal of Combinatorial Theory B, Band 100, 2010, S. 181–205
  4. ↑ Dan Archdeacon: A Kuratowski Theorem for the Projective Plane. Graph Theory, Band 5, 1981, S. 243–246
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.