How many conjectures can you stand: a survey

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

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
52 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 languageUndefined
Pages (from-to)57-75
Number of pages19
JournalGraphs and combinatorics
Volume28
Issue number1
DOIs
Publication statusPublished - 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, Haitze J. ; Ryjáček, Z. ; Vrána, P. / How many conjectures can you stand: a survey. In: Graphs and combinatorics. 2012 ; Vol. 28, No. 1. pp. 57-75.
@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",

}

How many conjectures can you stand: a survey. / Broersma, Haitze J.; Ryjáček, Z.; Vrána, P.

In: Graphs and combinatorics, Vol. 28, No. 1, 2012, p. 57-75.

Research output: Contribution to journalArticleAcademicpeer-review

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 -