Generation and properties of snarks
Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund, Klas Markström · 2016
Abstract. For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of nontrivial 3-regular graphs which cannot be 3-edge coloured. In the first part of this paper we present a new algorithm for gener-ating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for gen-erating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on n ≤ 36 vertices. Previously lists up to n = 28 vertices have been published. In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaeger’s Petersen colouring conjecture, which in turn implies that Fulkerson’s conjecture has no