Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks

Haitze J. Broersma, Gasper Fijavz, Tomas Kaiser, Roman Kuzel, Zdenek Ryjacek, Petr Vrana

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)
43 Downloads (Pure)

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 languageUndefined
Pages (from-to)6064-6077
Number of pages14
JournalDiscrete mathematics
Volume308
Issue numberWoTUG-31/24
DOIs
Publication statusPublished - Dec 2008

Keywords

  • METIS-254965
  • EWI-14553
  • Snark
  • Line graph
  • Hamiltonian graph
  • Dominating cycle
  • Cubic graph
  • Contractible graph
  • IR-62591

Cite this