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

Share/Save/Bookmark

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

[img] PDF
Restricted to UT campus only
: Request a copy
1MB
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.

Item Type:Article
Copyright:© 2008 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62591
Official URL:http://dx.doi.org/10.1016/j.disc.2007.11.026
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 254965