Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks
Broersma, Hajo and Fijavz, Gasper and Kaiser, Tomas and Kuzel, Roman and Ryjacek, Zdenek and Vrana, Petr (2008) Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks. Discrete Mathematics, 308 (24). pp. 6064-6077. ISSN 0012-365X
Restricted to UT campus only: Request a copy
|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.
|Copyright:||© 2008 Elsevier|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/62591|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 254965