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

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 languageUndefined
Article number10.1016/j.endm.2007.01.009
Pages (from-to)55-59
Number of pages5
JournalElectronic notes in discrete mathematics
Volume28
Issue number4542
DOIs
Publication statusPublished - 1 Mar 2007
Event6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications - Prague
Duration: 10 Jul 200616 Jul 2006

Keywords

  • Line graph
  • Snark
  • EWI-10372
  • METIS-241732
  • Hamiltonian graph
  • Contractible graph
  • Cubic graph
  • Dominating cycle
  • IR-61772

Cite this