Prof. Dr. Eckhard Steffen

PI, Beginn September 2024

Viele wichtige Fragestellungen der Graphentheorie (wie die 5-Fluss-Vermutung oder die Cycle-Double-Cover-Vermutung) können auf die Klasse der kubischen Graphen reduziert werden. In der Tat, es reicht aus, sie für brückenlose kubische Graphen zu lösen, die keine 3-Kanten-Färbung zulassen, den so genannten Snarks. Aufgrund ihrer herausgehobenen Bedeutung ist die Untersuchung von Snarks ein sehr aktives Forschungsgebiet der Graphentheorie. Viele der auf Snarks reduzierbaren Fragestellungen haben natürliche Verallgemeinerungen für r-reguläre Graphen mit r>3, so dass in den letzten Jahren diese Klasse von Graphen verstärkt in den Fokus mathematischer Forschung gerückt sind. In dem Projekt werden diese Graphen untersucht, um neue Erkenntnisse zur Wechselwirkung von Methoden und Eigenschaften zwischen dem Fall r=3 und dem allgemeinen Fall zu gewinnen. Dies geschieht unter Bezug auf die feinere Klassifizierung r-regulärer Graphen bezüglich paarweise disjunkter perfekter Matchings, welche für kubische Graphen nicht greift.

P.I., start Januar 2024 (5 Years)
Scientific Research Network, FWO (Belgium)

The scientific research network consists of the following working groups: Jan De Beule (Vrije Universiteit Brussel); Kris Coolsaet, Leo Storm (Universiteit Gent); Jan Goedgebeur (KU Leuven); Aida Abaid (Eindhoven University of Technology); Karen Aardal (TU Delft); Eric Opdam (University of Amsterdam); Eckhard Steffen (Paderborn University)

P.I., Laufzeit 01/2020 - 12/2024
DFG - Deutsche Forschungsgemeinschaft

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.