Karabáš, Ján, 1977- ; International Workshop on Combinatorial Algorithms (IWOCA). medzinárodný workshop (20. : 28.06.-02.07.2009 : Hradec nad Moravicí) 6-decomposition of snarks / Ján Karabáš, Edita Máčajová, Roman Nedela. -- 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>= 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. The paper 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.

In European Journal of Combinatorics. -- London : Academic Press, 2013. -- ISSN 0195-6698. -- ISSN 1095-9971. -- Vol. 34, no. 1 (2013), pp. 111-122

1. matematika 2. snark 3. 6-decomposition

I. Máčajová, Edita
II. Nedela, Roman, 1960-
III. European Journal of Combinatorics. -- Vol. 34, no. 1 (2013), pp. 111-122

51
BB301