Contractible subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for snarks

Haitze J. Broersma; Gasper Fijavz; Tomas Kaiser; Roman Kuzel; Zdenek Ryjacek; Petr Vrana

doi:10.1016/j.endm.2007.01.009

Contractible subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for snarks

Haitze J. Broersma, Gasper Fijavz, Tomas Kaiser, Roman Kuzel, Zdenek Ryjacek, Petr Vrana

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

8 Downloads (Pure)

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.

Original language	Undefined
Article number	10.1016/j.endm.2007.01.009
Pages (from-to)	55-59
Number of pages	5
Journal	Electronic notes in discrete mathematics
Volume	28
Issue number	4542
DOIs	https://doi.org/10.1016/j.endm.2007.01.009
Publication status	Published - 1 Mar 2007
Event	6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications - Prague Duration: 10 Jul 2006 → 16 Jul 2006

Keywords

Line graph
Snark
EWI-10372
METIS-241732
Hamiltonian graph
Contractible graph
Cubic graph
Dominating cycle
IR-61772

Access to Document

10.1016/j.endm.2007.01.009

http://eprints.eemcs.utwente.nl/secure2/10372/01/broersmaFijavz.pdf

Cite this

@article{f57d063adba6438088f7a5ee9814da93,

title = "Contractible subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for snarks",

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{\'a}Ŀ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{\'a}Ŀek in 1997.",

keywords = "Line graph, Snark, EWI-10372, METIS-241732, Hamiltonian graph, Contractible graph, Cubic graph, Dominating cycle, IR-61772",

author = "Broersma, \{Haitze J.\} and Gasper Fijavz and Tomas Kaiser and Roman Kuzel and Zdenek Ryjacek and Petr Vrana",

note = "10.1016/j.endm.2007.01.009 ; 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications ; Conference date: 10-07-2006 Through 16-07-2006",

year = "2007",

month = mar,

day = "1",

doi = "10.1016/j.endm.2007.01.009",

language = "Undefined",

volume = "28",

pages = "55--59",

journal = "Electronic notes in discrete mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "4542",

}

TY - JOUR

T1 - Contractible subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for snarks

AU - Broersma, Haitze J.

AU - Fijavz, Gasper

AU - Kaiser, Tomas

AU - Kuzel, Roman

AU - Ryjacek, Zdenek

AU - Vrana, Petr

N1 - 10.1016/j.endm.2007.01.009

PY - 2007/3/1

Y1 - 2007/3/1

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

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

KW - Line graph

KW - Snark

KW - EWI-10372

KW - METIS-241732

KW - Hamiltonian graph

KW - Contractible graph

KW - Cubic graph

KW - Dominating cycle

KW - IR-61772

U2 - 10.1016/j.endm.2007.01.009

DO - 10.1016/j.endm.2007.01.009

M3 - Article

SN - 1571-0653

VL - 28

SP - 55

EP - 59

JO - Electronic notes in discrete mathematics

JF - Electronic notes in discrete mathematics

IS - 4542

M1 - 10.1016/j.endm.2007.01.009

T2 - 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications

Y2 - 10 July 2006 through 16 July 2006

ER -