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.
Original language | Undefined |
---|---|
Pages (from-to) | 6064-6077 |
Number of pages | 14 |
Journal | Discrete mathematics |
Volume | 308 |
Issue number | WoTUG-31/24 |
DOIs | |
Publication status | Published - Dec 2008 |
Keywords
- METIS-254965
- EWI-14553
- Snark
- Line graph
- Hamiltonian graph
- Dominating cycle
- Cubic graph
- Contractible graph
- IR-62591