Toughness and Triangle-Free Graphs

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

Research output: Contribution to journalArticleAcademic

11 Citations (Scopus)
74 Downloads (Pure)

Abstract

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
Volume65
Issue number2
DOIs
Publication statusPublished - 1995

Fingerprint

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

Cite this