Doppel-Kreisüberdeckungen, Bipartite Minoren und Snarks

Die Cycle Double Cover Conjecture (CDCC) und die Nowhere-Zero 5-Flow Conjecture (NZ5FC) gehören zu den wichtigsten ungelösten Problemen der Graphentheorie. CDCC: Jeder brückenlose Graph G enthält eine Menge S von Kreisen, sodass jede Kante von G genau zwei Kreisen in S angehört. NZ5FC: Jeder brückenlose Graph besitzt einen nowhere-zero 5-flow. Für beide Vermutungen genügt es, 3-reguläre Graphen zu betrachten, die nicht 3-Kanten-färbbar sind. Dieses Projekt soll sich mit Problemen beschäftigen, die in engem Zusammenhang mit diesen Vermutungen stehen. Die folgenden drei Forschungsrichtungen umreissen die wichtigsten Ziele dieses Projekts: 1. Beweis der CDCC sowie der Verallgemeinerten Kompatibilitäts-Vermutung (eine neue Vermutung, die in engem Zusammenhang mit der CDCC steht) für neue Klassen brückenloser Graphen; z.b. Verallgemeinerungen von Circle Graphs, Graphen mit einer Darstellung in der Ebene, die eine "beschränkte Kreuzungs-Distanz" besitzt, etc. 2. Beweis neuer struktureller Resultate in brückenlosen kubischen Graphen durch die Erforschung bipariter spannender Minoren. 3. Entwicklung neuer Konstruktionsmethoden von Snarks mit grosser Taillenweite und kleiner Knotenzahl.

Die Cycle Double Cover Conjecture (CDCC - Kreis-Doppelüberdeckung-Vermutung) ist eines der bedeutendsten ungelösten Probleme der Graphentheorie. Sie besagt, daß in jedem brückenlosen Graphen eine Familie von Kreisen derart existiert, daß jede Kante genau zwei Elementen dieser Familie angehört. Bist jetzt ist die CDCC sowie Variationen dieser Vermutung nur für verschiedene Graphenklassen gelöst worden. In diesem Projekt wurden Resultate bewiesen, die Anwendungen bezüglich der CDCC ergaben, oder diese und Variationen davon für einige nicht-triviale Graphenklassen lösen. Man kann auf verschiedene Weisen die CDCC zu lösen versuchen. Eine läuft darauf hinaus, eine Struktur zu bestimmen, deren Existenz in 3-fach zusammenhängenden kubischen Graphen die Gültigkeit der CDCC nach sich zieht. Diese Vorgangsweise resultierte bereits früher in der Formulierung mehrerer Probleme und Vermutungen durch andere Graphentheoretiker. Diese Formulierungen beruhen auf der Erwartung, daß ein 3-fach zusammenhängender kubischer Graph in ein Matching und spezielle 2-fach zusammenhängende Teilgraphen zerlegt werden kann. Wir konnten zeigen, daß die genannten Probleme und Vermutungen selbst in einer abgeschwächten Form nicht einer positiven Lösung zugeführt werden können. Es sei festgehalten, daß dieses Resultat für viele Probleme in kubischen Graphen von Bedeutung ist, da es ein allgemeines Resultat bezüglich Strukturen in kubischen Graphen ist. Der Petersen Graph is ein zyklisch 5-fach kanten-zusammenhängender Permutation-Snark (c5c-PS), d.h., er verfügt über einen 2-Faktor aus zwei diagonalfreien Kreisen. Bis vor kurzem war unbekannt, ob es endlich oder unendlich viele solche Snarks gibt. Wir konstruierten die erste unendliche Klasse S von c5c-PSs. Weiters konnten wir beweisen, daß jeder Graph G in S interessante Eigenschaften mit dem Petersen Graphen gemeinsam hat. Insbesondere konnte nachgewiesen werden, daß der Permutation-2-Faktor keiner CDC von G angehört. Daraus folgen Gegenbeispiele zu mehreren Vermutungen bezüglich CDCs. Es sei darauf hingewiesen, daß man nicht weiß, ob es andere c5c-PSs gibt. Im Rahmen des Projekts wurde auch gezeigt, daß ein Snark mit einem 2-Faktor aus zwei Kreisen C und C, die nicht diagonalfrei sein müssen, eine CDC besitzt, welche C oder C enthält. Analoge Resultate konnten für weitere Graphenklassen erzielt werden. Die Starke CDCC besagt, dass jeder gegebene Kreis eines kubischen Graphen einer CDC angehört. Diese Vermutung war als wahr für spezielle Graphen-klassen wie die hypohamiltonschen Snarks und 3-kantenfärbbare Graphen erkannt worden. Für jeden anderen Snark, der nicht hypohamiltonsch ist, war bislang kein potentiell gangbarer Weg bekannt, wonach jeder gegebene Kreis C in einer CDC enthalten ist. Wir entwickelten eine neue Technik, die mehr als das beweisen soll, nämlich, daß C in einer 5CDC enthalten ist. Wir bewiesen eine Charakterisierung, wann C in einer 5CDC enthalten ist, und führten die bislang stärkste Version der (nicht orientierbaren) CDCC ein: die starke 5CDCC. Hinweise für die Gültigkeit dieser neuen Vermutung wurden unter anderem durch den Beweis erzielt, wonach ein beliebiger fester Kreis eines Flower Snark oder Goldberg Snark in einer 5CDC enthalten ist. Außerdem wurde die starke 5CDCC für kleine kubische Graphen kürzlich durch andere Graphentheoretiker mithilfe von Computern verifiziert (es sei darauf hingewiesen, daß die Flower Snarks und Goldberg Snarks die bekanntesten unendlichen Klassen von Snarks sind). Wir studierten auch Probleme zur Unabhängigkeitszahl in speziellen Klassen 4-regulärer Graphen, Nowhere-Zero Fluß-Probleme, mehrere Konstruktionstechniken bezüglich Snarks sowie planarisierende Pseudomatchings. Dazu wurden mehrere, jedoch nicht signifikante Resultate erzielt.