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 with 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 |
---|---|
Article number | 10.1016/j.endm.2007.01.009 |
Pages (from-to) | 55-59 |
Number of pages | 5 |
Journal | Electronic notes in discrete mathematics |
Volume | 28 |
Issue number | 4542 |
DOIs | |
Publication status | Published - 1 Mar 2007 |
Event | 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications - Prague Duration: 10 Jul 2006 → 16 Jul 2006 |
Keywords
- Line graph
- Snark
- EWI-10372
- METIS-241732
- Hamiltonian graph
- Contractible graph
- Cubic graph
- Dominating cycle
- IR-61772