Contractible Subgraphs,Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks |
| |
| Institution: | 1. Department of Computer Science, University of Durham, Science Laboratories, South Road, Durham, DH1 3LE England;2. Faculty of Computer and Information Science, University of Ljubljana, Tržaška 25, 1000 Ljubljana, Slovenia;3. Department of Mathematics, University of West Bohemia, and Institute for Theoretical Computer Science (ITI), Charles University, P.O. Box 314, 306 14 Pilsen, Czech Republic;1. Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany;2. School of Engineering and Computing Sciences, Durham University, UK |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
