2012-05-14
dr. Roman Nedela (Matej Bel University, Slovakia)
6-decompositions of snarks
A snark is a cubic graph with no proper $3$-edge-colouring. In 1996, Nedela and \v Skoviera proved the following theorem:
Let $G$ be a snark with an $k$-edge-cut, $k\geq 2$, whose removal leaves two
$3$-edge-colourable components $M$ and $N$. Then both $M$ and $N$ can be completed to two snarks $\tilde M$ and $\tilde N$ of order not exceeding that of $G$ by adding at most $\kappa(k)$ vertices, where the number $\kappa(k)$ only depends on $k$. The known values of the function $\kappa(k)$ are $\kappa(2)=0$, $\kappa(3)=1$, $\kappa(4)=2$ (Goldberg, 1981), and $\kappa(5)=5$ (Cameron, Chetwynd, Watkins, 1987). The value $\kappa(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 $\kappa(6)$ is the last important value to determine. Our talk is aimed attacking the problem of determining $\kappa(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 $\kappa(6)\geq 20$ and there are strong restrictions on the structure of (possibly) missing complements.
Part of the proofs are computer assisted.
$3$-edge-colourable components $M$ and $N$. Then both $M$ and $N$ can be completed to two snarks $\tilde M$ and $\tilde N$ of order not exceeding that of $G$ by adding at most $\kappa(k)$ vertices, where the number $\kappa(k)$ only depends on $k$. The known values of the function $\kappa(k)$ are $\kappa(2)=0$, $\kappa(3)=1$, $\kappa(4)=2$ (Goldberg, 1981), and $\kappa(5)=5$ (Cameron, Chetwynd, Watkins, 1987). The value $\kappa(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 $\kappa(6)$ is the last important value to determine. Our talk is aimed attacking the problem of determining $\kappa(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 $\kappa(6)\geq 20$ and there are strong restrictions on the structure of (possibly) missing complements.
Part of the proofs are computer assisted.
