Name
Abstract | ||
|---|---|---|
A snark is a cubic graph with no proper 3-edge-colouring. In 1996, Nedela and 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 M@? and N@? of order not exceeding that of G by adding at most @k(k) vertices, where the number @k(k) only depends on k. The known values of the function @k(k) are @k(2)=0, @k(3)=1, @k(4)=2 (Goldberg, 1981) [6], and @k(5)=5 (Cameron et al. 1987) [4]. The value @k(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 @k(6) is the last important value to determine. The paper is aimed attacking the problem of determining @k(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 @k(6)=20 and there are strong restrictions on the structure of (possibly) missing complements. Part of the proofs are computer assisted. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ejc.2012.07.019 | Eur. J. Comb. |
Keywords | Field | DocType |
last important value,known value,strong restriction,cubic graph,following theorem,proper 3-edge-colouring,3-edge-colourable component,snarks m,7-cyclically-connected snarks,colour property | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Cubic graph,Mathematical proof,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
34 | 1 | 0195-6698 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| JáN Karabáš | 1 | 3 | 2.19 |
| Edita MáčAjová | 2 | 63 | 11.04 |
| Roman Nedela | 3 | 392 | 47.78 |