|
|||||
|
|
Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks |
|
| Authors: | Hajo Broersma,Roman Ku?el,Zdeněk Ryjá ?ek,Petr Vrá na |
| Affiliation: | a Department of Computer Science, University of Durham, Science Laboratories, South Road, Durham, DH1 3LE, England, United Kingdom b Faculty of Computer and Information Science, University of Ljubljana, Tr?aška 25, 1000 Ljubljana, Slovenia c Department of Mathematics, University of West Bohemia, Czech Republic d Institute for Theoretical Computer Science (ITI), Charles University, P.O. Box 314, 306 14 Pilsen, Czech Republic |
| 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. |
| Keywords: | Dominating cycle Contractible graph Cubic graph Snark Line graph Hamiltonian graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |