Toughness in graphs - A survey

Douglas Bauer, Haitze J. Broersma, Edward Schmeichel

Research output: Contribution to journalArticleAcademicpeer-review

70 Citations (Scopus)


In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology and notation, and then try to organize the work into a few self explanatory categories. These categories are circumference, the disproof of the 2-tough conjecture, factors, special graph classes, computational complexity, and miscellaneous results as they relate to toughness. We complete the survey with some tough open problems!
Original languageUndefined
Article number10.1007/s00373-006-0649-0
Pages (from-to)1-35
Number of pages35
JournalGraphs and combinatorics
Issue number10/1
Publication statusPublished - Apr 2006


  • IR-63724
  • Hamiltonian graph
  • Chordal graph
  • (Hamilton) cycle
  • Factor
  • METIS-237666
  • Computational Complexity
  • Circumference
  • Traceable graph
  • Triangle-free graph
  • Toughness
  • EWI-8329
  • k-Factor
  • Planar graph
  • t-Tough graph

Cite this