Lexikon der Mathematik: Robertson-Seymour, Graph-Minor-Satz von
bestätigt die Vermutung von Wagner (Wagner, Vermutung von) und sagt aus, daß es für jede unendliche Folge G1, G2,…von Graphen Indizes i< j so gibt, daß Gi ein Minor (Minor eines Graphen) von Gj ist.
Definiert man eine Relation „≤“ auf der Menge aller Graphen dadurch, daß G ≤ G′ genau dann gilt, wenn G ein Minor von G′ ist, dann sagt der Satz von Robertson-Seymour aus, daß ≤ eine WohlQuasi-Ordnung auf der Menge aller Graphen ist.
Der Beweis dieses Satzes ist in einer Reihe von über 20 Artikeln von N. Robertson und P. Seymour unter dem Namen „graph-minor-project“ enthalten, die seit 1983 in einem Zeitraum von über 15 Jahren erschienen sind, und zählt zu den schwierigsten und tiefsten Beweisen in der Graphentheorie. Seine Autoren entwickelten für ihn die Theorie der Minoren und Baumweite von Graphen.
Weitere wichtige Ergebnisse dieser Theorie sind z. B. folgende Aussagen:
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.