id: 06106899
dt: j
an: 06106899
au: Karabáš, Ján; Máčajová, Edita; Nedela, Roman
ti: 6-decomposition of snarks.
so: Eur. J. Comb. 34, No. 1, 111-122 (2013).
py: 2013
pu: Elsevier Science (Academic Press), London
la: EN
cc: 
ut: 
ci: 
li: doi:10.1016/j.ejc.2012.07.019
ab: Summary: 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\ge 2$, whose removal leaves two
    3-edge-colourable components $M$ and $N$. Then both $M$ and $N$ can be
    completed to two snarks $\sim {M}$ and $\sim {N}$ 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)\ge 20$ and there are strong restrictions on the
    structure of (possibly) missing complements. Part of the proofs are
    computer assisted.
rv: