Überdeckungen und Kerne von r-Graphen

• Antragsteller: Professor Dr. Eckhard Steffen
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2013 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 240639532

Für viele harte offene Probleme der Graphentheorie würde es genügen, diese für kubische (3-reguläre) Graphen zu lösen, um sie allgemein zu lösen. Beispiele sind die 4-Farben-Vermutung (nun bewiesen), Vermutungen zu Kreis- oder Matching-Überdeckungen, Einbettungen in 2-Mannigfaltigkeiten oder die 5-Fluss-Vermutung. Viele dieser Probleme sind leicht zu lösen für kubische Graphen mit chromatischem Index 3. Folglich ist die Klasse der brückenlosen, nicht 3-Kanten-färbbaren kubischen Graphen, die sogenannten Snarks, die Klasse der möglichen Gegenbeispiele für diese Vermutungen. Eines der Hauptprobleme beim Beweis für Aussagen über Snarks ist die Definition geeigneter struktureller Parameter für die jeweilige Fragestellung. Es gibt eine Vielzahl von Arbeiten über Reduktionen von Snarks auf kleinere Graphen oder über Invarianten, die messen wie kompliziert ein Snark ist; das soll heißen, wie weit er davon entfernt ist 3-Kanten-färbbar zu sein. Viele positive Ergebnisse zu den oben genannten Problemen wurden erzielt für Snarks, die zusätzliche Bedingungen bzgl. solcher Invarianten erfüllen. In [52] führen wir den Begriff des Kerns eines kubischen Graphen ein. Sei G ein solcher Graph und M_1, M_2 und M_3 drei paarweise verschiedene 1-Faktoren von G. Sei M die Menge der Kanten von G, die in mehr als einem 1-Faktor und U die Menge der Kanten, die in keinem der drei 1-Faktoren liegen und k = |U|. Der k-Kern von G ist der Untergraph G_c von G, der durch die Vereinigung der Mengen M und U induziert wird. Die Untersuchung von k-Kernen kubischer Graphen lieferte überraschende neue Ergebnisse zu strukturellen Eigenschaften von Snarks. Sei r eine positive ganze Zahl. Ein r-Graph ist ein r-regulärer Graph, in dem es für jede Eckenmenge S ungerader Kardinalität mindestens r Kanten gibt, die zu genau einer Ecke aus S inzident sind.Das Ziel des beantragten Forschungsprojektes ist, eine Theorie der Kerne von r-Graphen zu entwickeln. Den Schwerpunkt der Arbeiten wird die Untersuchung kubischer Graphen bilden. Die Vermutungen von Berge-Fulkerson, Fan und Raspaud, die Doppelte-Kreis-Überdeckungs-Vermutung und kürzeste Kreisüberdeckungen werden untersucht. Einige dieser Vermutungen können als Aussagen über Kerne in kubischen Graphen formuliert werden. Interessanterweise gibt es sehr natürliche Aussagen über Kerne in kubischen Graphen, die schwächer sind als diese Vermutungen. Ein Ziel des Projektes ist, Ergebnisse zu diesen Vermutungen zu erzielen.Die Ergebnisse für kubische Graphen sollen auf r-Graphen verallgemeinert werden. Hier werden wir uns auf die verallgemeinerte Berge-Fulkerson- und die r-Graph-Vermutung von Seymour konzentrieren. Darüber hinaus wollen wir Ergebnisse über Kerne von r-Graphen nutzen, um Zerlegungssätze für Multigraphen mit großem chromatischem Index zu beweisen.

• DFG-Verfahren: Sachbeihilfen