Toughness and Triangle-Free Graphs

D. Bauer, J. van den Heuvel, E. Schmeichel

Research output: Contribution to journalArticleAcademic

12 Citations (Scopus)
96 Downloads (Pure)


In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t.
Original languageEnglish
Pages (from-to)208-221
JournalJournal of Combinatorial Theory, Series B
Issue number2
Publication statusPublished - 1995


Dive into the research topics of 'Toughness and Triangle-Free Graphs'. Together they form a unique fingerprint.

Cite this