Snarks without small cycles (Q1924136)

Snarks are non-trivial (i.e., cyclically 4-edge-connected) 3-regular graphs whose edges cannot be colored with three colors. Jaeger and Swart conjectured that any snark has girth (the length of the shortest cycle) at most 6. This problem is also known as the girth conjecture of snarks. The aim of this paper is to give a negative solution of this conjecture and to construct snarks with arbitrarily large girths. For instance, using known constructions of cubic graphs with large girths, we can explicitly construct cyclically 5-edge-connected snarks of order \(n\) and with girth at least \(({4\over 3}\pm o(1))\log_2 n\), what is an asymptotically optimal result.