How many conjectures can you stand: a survey

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

doi:10.1007/s00373-011-1090-6

How many conjectures can you stand: a survey

Haitze J. Broersma, Z. Ryjáček, P. Vrána

Discrete Mathematics and Mathematical Programming

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

14 Citations (Scopus)

62 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	Undefined
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
IR-79404
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
EWI-21070
MSC-05C35
MSC-05C38
MSC-05C45
METIS-293520
Claw-free graph

Cite this

Broersma, H. J., Ryjáček, Z., & Vrána, P. (2012). How many conjectures can you stand: a survey. Graphs and combinatorics, 28(1), 57-75. https://doi.org/10.1007/s00373-011-1090-6

@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, IR-79404, 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, EWI-21070, MSC-05C35, MSC-05C38, MSC-05C45, METIS-293520, Claw-free graph",

author = "Broersma, {Haitze J.} and Z. Ryj{\'a}ček and P. Vr{\'a}na",

note = "Open Access",

year = "2012",

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

language = "Undefined",

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, Haitze J.

AU - Ryjáček, Z.

AU - Vrána, P.

N1 - Open Access

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 - IR-79404

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 - EWI-21070

KW - MSC-05C35

KW - MSC-05C38

KW - MSC-05C45

KW - METIS-293520

KW - Claw-free graph

U2 - 10.1007/s00373-011-1090-6

DO - 10.1007/s00373-011-1090-6

M3 - Article

VL - 28

SP - 57

EP - 75

JO - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 1

ER -

Access to Document

10.1007/s00373-011-1090-6

fulltext-9
open
fulltext-9
open