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.