How many conjectures can you stand? A survey

H.J. Broersma; Z. Ryjáček; P. Vrána

doi:10.1007/s00373-011-1090-6

How many conjectures can you stand? A survey

H.J. Broersma^*, Z. Ryjáček, P. Vrána

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

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

18 Citations (Scopus)

125 Downloads (Pure)

Abstract

We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting concepts, techniques, results and equivalent conjectures.

Original language	English
Pages (from-to)	57-75
Number of pages	19
Journal	Graphs and combinatorics
Volume	28
Issue number	1
DOIs	https://doi.org/10.1007/s00373-011-1090-6
Publication status	Published - 2012

Keywords

Contractible graph
Closure
Cyclically 4-edge-connected
Cubic graph
Collapsible graph
Hamilton-connected
Hamiltonian graph
Dominating closed trail
Dominating cycle
Essentially 4-edge-connected
Line graph
Snark
Supereulerian graph
MSC-05C35
MSC-05C38
MSC-05C45
Claw-free graph

Access to Document

10.1007/s00373-011-1090-6Licence: CC BY-NC

ArticleFinal published version, 445 KBLicence: CC BY-NC

Cite this

@article{82c4edb30df3463d924209c8315c0a07,

title = "How many conjectures can you stand? A survey",

abstract = "We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting concepts, techniques, results and equivalent conjectures.",

keywords = "Contractible graph, Closure, Cyclically 4-edge-connected, Cubic graph, Collapsible graph, Hamilton-connected, Hamiltonian graph, Dominating closed trail, Dominating cycle, Essentially 4-edge-connected, Line graph, Snark, Supereulerian graph, MSC-05C35, MSC-05C38, MSC-05C45, Claw-free graph",

author = "H.J. Broersma and Z. Ryj{\'a}{\v c}ek and P. Vr{\'a}na",

year = "2012",

doi = "10.1007/s00373-011-1090-6",

language = "English",

volume = "28",

pages = "57--75",

journal = "Graphs and combinatorics",

issn = "0911-0119",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - How many conjectures can you stand? A survey

AU - Broersma, H.J.

AU - Ryjáček, Z.

AU - Vrána, P.

PY - 2012

Y1 - 2012

N2 - We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting concepts, techniques, results and equivalent conjectures.

AB - We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting concepts, techniques, results and equivalent conjectures.

KW - Contractible graph

KW - Closure

KW - Cyclically 4-edge-connected

KW - Cubic graph

KW - Collapsible graph

KW - Hamilton-connected

KW - Hamiltonian graph

KW - Dominating closed trail

KW - Dominating cycle

KW - Essentially 4-edge-connected

KW - Line graph

KW - Snark

KW - Supereulerian graph

KW - MSC-05C35

KW - MSC-05C38

KW - MSC-05C45

KW - Claw-free graph

U2 - 10.1007/s00373-011-1090-6

DO - 10.1007/s00373-011-1090-6

M3 - Article

SN - 0911-0119

VL - 28

SP - 57

EP - 75

JO - Graphs and combinatorics

JF - Graphs and combinatorics

IS - 1

ER -

How many conjectures can you stand? A survey

Abstract

Keywords

Access to Document

Fingerprint

Cite this