Number of the records: 1
6-decomposition of snarks
SYS 0172963 LBL 02127^^^^^2200241^^^450 005 20240618111547.3 014 $a 000310110100011 $2 WOS CC. SCIE 014 $a 000310110100011 $2 WOS CC. CPCI-S 014 $a 2-s2.0-84866992270 $2 SCOPUS 017 70
$a 10.1016/j.ejc.2012.07.019 $2 DOI 100 $a 20121106d2013 m y slo 03 ba 101 0-
$a eng 200 1-
$a 6-decomposition of snarks $f Ján Karabáš, Edita Máčajová, Roman Nedela 330 0-
$a 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. 463 -1
$1 001 umb_un_cat*0309647 $1 011 $a 0195-6698 $1 011 $a 1095-9971 $1 200 1 $a European Journal of Combinatorics $v Vol. 34, no. 1 (2013), pp. 111-122 $1 210 $a London $c Academic Press $d 2013 606 $3 umb_un_auth*0036218 $a matematika $X mathematics 606 0-
$3 umb_un_auth*0087101 $a snark 606 0-
$3 umb_un_auth*0210805 $a 6-decomposition 615 $n 51 $a Matematika 675 $a 51 700 -0
$3 umb_un_auth*0031992 $a Karabáš $b Ján $f 1977- $p UMBFP12 $9 34 $4 070 $T Inštitút matematiky a informatiky 701 -1
$3 umb_un_auth*0210806 $a Máčajová $b Edita $4 070 $9 33 701 -0
$3 umb_un_auth*0001645 $a Nedela $b Roman $f 1960- $p UMBFP10 $9 33 $4 070 $T Katedra matematiky 710 11
$3 umb_un_auth*0305253 $a International Workshop on Combinatorial Algorithms (IWOCA) $b medzinárodný workshop $d 20. $e Hradec nad Moravicí $f 28.06.-02.07.2009 801 $a SK $b BB301 $g AACR2 $9 unimarc sk T85 $x existuji fulltexy
Number of the records: 1