Some snarks are worse than others

Abstract

Many conjectures and open problems in graph theory can either be reduced to cubic graphs or are directly stated for cubic graphs. Furthermore, it is known that for a lot of problems, a counterexample must be a snark, i.e. a bridgeless cubic graph which is not 3--edge-colourable. In this paper we deal with the fact that the family of potential counterexamples to many interesting conjectures can be narrowed even further to the family ${\mathcal{S}}_{\ge 5}$ of bridgeless cubic graphs whose edge set cannot be covered with four perfect matchings. The Cycle Double Cover Conjecture, the Shortest Cycle Cover Conjecture and the Fan-Raspaud Conjecture are examples of statements for which ${\mathcal{S}}_{\ge 5}$ is crucial. In this paper, we study parameters which have the potential to further refine ${\mathcal{S}}_{\ge 5}$ and thus enlarge the set of cubic graphs for which the mentioned conjectures can be verified. We show that ${\mathcal{S}}_{\ge 5}$ can be naturally decomposed into subsets with increasing complexity, thereby producing a natural scale for proving these conjectures. More precisely, we consider the following parameters and questions: given a bridgeless cubic graph, (i) how many perfect matchings need to be added, (ii) how many copies of the same perfect matching need to be added, and (iii) how many 2--factors need to be added so that the resulting regular graph is Class I? We present new results for these parameters and we also establish some strong relations between these problems and some long-standing conjectures.

27 pages, 16 figures

References in corpus (7)

• Generation and Properties of Snarks
• 1-factor and cycle covers of cubic graphs
• On the perfect matching index of bridgeless cubic graphs
• On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings
• On essentially 4-edge-connected cubic bricks
• Edge colorings and circular flows on regular graphs
• An algorithm and new bounds for the circular flow number of snarks

Cited by in corpus (1)

• Ban--Linial's Conjecture and treelike snarks