6-decomposition of snarks

A snark is a cubic graph with no proper 3-edge-colouring. In 1996, Nedela and Škoviera proved the following theorem: Let G be a snark with an k-edge-cut, k≥2, whose removal leaves two 3-edge-colourable components M and N. Then both M and N can be completed to two snarks M̃ and Ñ of order not exceeding that of G by adding at most κ(k) vertices, where the number κ(k) only depends on k. The known values of the function κ(k) are κ(2)=0, κ(3)=1, κ(4)=2 (Goldberg, 1981) [6], and κ(5)=5 (Cameron et al. 1987) [4]. The value κ(6) is not known and is apparently difficult to calculate. In 1979, Jaeger conjectured that there are no 7-cyclically-connected snarks. If this conjecture holds true, then κ(6) is the last important value to determine. The paper is aimed attacking the problem of determining κ(6) by investigating the structure and colour properties of potential complements in 6-decompositions of snarks. We find a set of 14 complements that suffice to perform 6-decompositions of snarks with at most 30 vertices. We show that if this set is not complete to perform 6-decompositions of all snarks, then κ(6)≥20 and there are strong restrictions on the structure of (possibly) missing complements. Part of the proofs are computer assisted.