Toughness and Triangle-Free Graphs


Bauer, D. and Heuvel, J. van den and Schmeichel, E. (1995) Toughness and Triangle-Free Graphs. Journal of Combinatorial Theory, Series B, 65 (2). pp. 208-221. ISSN 0021-9800

open access
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.
Item Type:Article
Copyright:© 1995 Elsevier Science
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page