Authors
Citation
D. Bauer et al., TOUGHNESS AND TRIANGLE-FREE GRAPHS, J COMB TH B, 65(2), 1995, pp. 208-221
Citations number
17
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
65
Issue
2
Year of publication
1995
Pages
208 - 221
Database
ISI
SICI code
0095-8956(1995)65:2<208:TATG>2.0.ZU;2-N
Abstract
In this paper, we prove that there exist triangle-free graphs with arb
itrarily large toughness, thereby settling a longstanding open questio
n. 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. (C
) 1995 Academic Press, Inc.