# 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 (2007) *Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks.* Electronic Notes in Discrete Mathematics, 28 . pp. 55-59. ISSN 1571-0653

PDF Restricted to UT campus only: Request a copy 156Kb |

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. |

Item Type: | Article |

Copyright: | © 2007 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/61772 |

Official URL: | http://dx.doi.org/10.1016/j.endm.2007.01.009 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 241732