Cycle Double Covers, Bipartizing Matchings and Snarks

The Cycle Double Cover Conjecture (CDCC) and the Nowhere Zero 5-flow Conjecture (NZ5FC) belong to the most important conjectures in graph theory. CDCC: Every bridgeless graph G has a collection S of cycles such that each edge of G is covered by exactly two cycles of S. NZ5FC: Every bridgeless graph has a nowhere zero 5-flow. For both conjectures it suffices to consider 3-regular graphs which are not 3-edge colorable. This project investigates problems which are closely related to these conjectures. The following three parts form the main scientific goals of this project: 1. Verification of the CDCC and the Generalized Compatibility Conjecture which is a new related conjecture to the CDCC for new classes of bridgeless graphs; for instance generalizations of circle graphs, graphs which admit drawings in the plane with "limited crossing distance", etc. 2. Achieving new structural results with respect to bridgeless cubic graphs by the investigation of bipartite spanning minors. 3. Development of new construction methods which give rise to snarks with large girth and small order.

The Cycle Double Cover Conjecture (CDCC) is one of the outstanding conjectures in graph theory. It claims that every bridgeless graph contains a family of circuits such that every edge of the graph belongs to precisely two elements of that family. The CDCC and variations of it have so far only been proved for various classes of graphs. Here, many results were obtained which had applications with respect to the CDCC or solved the CDCC and variations of it for non-trivial classes of graphs. There are several approaches to solve the CDCC. One of them is to search for a structure whose existence in 3-connected cubic graphs solves the CDCC. This approach resulted in the formulation of several problems and conjectures in this direction, by other graph theorists. These formulations are based on the expectation that a 3-connected cubic graph can be decomposed into a matching and 2-connected subgraphs satisfying a certain parity condition, and a hamiltonian condition. We showed that even if one weakens the hamiltonian condition considerably, these conjectures and problems have no affirmative answer. Note that this result is relevant for many problems concerning cubic graphs since it is a general result about structures in cubic graphs. The Petersen graph is a cyclically 5-edge-connected permutation snark (c5c-PS), i.e. it has a 2-factor consisting of two chordless circuits. Until recently, it was unknown whether there exist finitely or infinitely many snarks of this type. We constructed the first infinite class S of c5c-PS`s. Moreover, we proved that every graph G in S shares interesting properties with the Petersen graph. In particular, we showed that the permutation 2-factor of G is not part of any CDC of G. This results in counterexamples to several conjectures related to CDCs. Note that it is not known whether other c5c-PS exist apart from the constructed ones. Within the project it was also shown that if a snark has a 2-factor of exactly two circuits, C and C` say, which need not be chordless, then there exists a CDC containing one of C and C`. Analogous results were obtained for other classes of graphs. The strong CDCC states that for every given circuit C of a cubic graph, there is a CDC which contains C. It was known that this conjecture holds for special classes of graphs, such as hypohamiltonian snarks and 3-edge- colorable graphs. For any other snark which is not hypohamiltonian, it was not known how to show in a reasonable way that every given circuit C is contained in a CDC. We developed a new technique which aims at showing more than that, namely that C is contained in a 5CDC. We established a characterization when a ciruit is contained in a 5CDC, and introduced the so far strongest version of the (non oriented) CDCC: the strong 5CDCC. Evidence for the validity of this new conjecture was given by showing that for every circuit C of G where G is either a Flower or Goldberg snark, there exists a 5CDC containing C. Moreover, the strong 5CDCC has already been verified by other graph theorists via computer application for cubic graphs of small order (note that the Flower and Goldberg snarks form the best known infinite classes of snarks). We also studied the independence number problems in special classes of 4-regular graphs, nowhere-zero flow problems, several construction techniques for snarks and planarizing pseudo matchings. There, minor results have been achieved.