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 them. Furthermore, it is known that for a lot of problems, a counterexample must be a snark, that is, 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 S≥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 S≥5 is crucial. In this paper we study parameters which have the potential to further refine S≥5 and thus enlarge the set of cubic graphs for which the mentioned conjectures can be verified. We show that S≥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.