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

Hajo 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

Hajo 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	English
Pages (from-to)	55-59
Number of pages	5
Journal	Electronic notes in discrete mathematics
Volume	28
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
Hamiltonian graph
Contractible graph
Cubic graph
Dominating cycle

Access to Document

10.1016/j.endm.2007.01.009

1 Article

Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks
Broersma, H., Fijavz, G., Kaiser, T., Kuzel, R., Ryjáček, Z. & Vrana, P., Dec 2008, In: Discrete mathematics. 308, 24, p. 6064-6077 14 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
15 Citations (Scopus)

238 Downloads (Pure)

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, Hamiltonian graph, Contractible graph, Cubic graph, Dominating cycle",

author = "Hajo Broersma and Gasper Fijavz and Tomas Kaiser and Roman Kuzel and Zdenek Ryjacek and Petr Vrana",

year = "2007",

month = mar,

day = "1",

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

language = "English",

volume = "28",

pages = "55--59",

journal = "Electronic notes in discrete mathematics",

issn = "1571-0653",

publisher = "Elsevier",

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

}

TY - JOUR

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

AU - Broersma, Hajo

AU - Fijavz, Gasper

AU - Kaiser, Tomas

AU - Kuzel, Roman

AU - Ryjacek, Zdenek

AU - Vrana, Petr

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 - Hamiltonian graph

KW - Contractible graph

KW - Cubic graph

KW - Dominating cycle

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

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

Y2 - 10 July 2006 through 16 July 2006

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Research output

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

Cite this