Faktoren in Graphen

Kantenfärbungen und Faktoren von Graphen sind klassische Gebiete der Graphentheorie. Frühe und die Graphentheorie prägende Sätze, wie z.B. der Satz von König (1916) oder Satz von Petersen (1891) machen Aussagen über Kantenfärbungen und Faktoren von Graphen. Besonderes Interesse gilt Faktoren von regulären Graphen. Vizing (1965) zeigte, dass die minimale Anzahl von Farben, mit denen die Kanten eines einfachen Graphen mit maximalem Eckengrad k gefärbt werden können entweder gleich k oder k+1 ist. Das Ergebnis teilt die Klasse der einfachen Graphen in zwei Klassen ein; G ist Klasse 1 falls G mit k Farben Kanten-färbbar ist und Klasse 2 sonst. Für keine der beiden Klassen gibt es Charakterisierungen und es ist ein NP-vollständiges Problem zu entscheiden, ob ein Graph mit k Farben färbbar ist, sogar für 3-reguläre Graphen (Holyer 1981). Es ist wenig über die Struktur von Klasse 2 Graphen bekannt. Ein Ziel des beantragten Forschungsprojektes ist es, hier neue Einsichten zu gewinnen. Aufbauend auf dem Ergebnis, dass jeder kritische Klasse 2 Graph sehr spezielle [1,2]-Faktoren hat, sollen die Methoden weiterentwickelt werden, um Vizings Vermutungen zu kritische Graphen zu approximieren. Erkenntnisse aus dem Studium kritischer Graphen sollen weiter genutzt werden, um Aussagen über Faktoren von r-Graphen, insbesondere von planaren r-Graphen, und auch von t-zusammenhängenden r-regulären Graphen zu beweisen. Der Schwerpunkt liegt auf der Untersuchung des Verhältnisses zwischen Kantenzusammenhang und der Existenz regulärer Faktoren.