?berdeckungen und Kerne von r-Graphen

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.