Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650328 | Discrete Mathematics | 2008 | 14 Pages |
Abstract
We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjáček and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjáček in 1997.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hajo Broersma, Gašper Fijavž, Tomáš Kaiser, Roman Kužel, Zdeněk Ryjáček, Petr Vrána,