A NOTE ON MAXIMAL TRIANGLE-FREE GRAPHS

Authors
GODDARD W KLEITMAN DJ
Citation
W. Goddard et Dj. Kleitman, A NOTE ON MAXIMAL TRIANGLE-FREE GRAPHS, Journal of graph theory, 17(5), 1993, pp. 629-631
Citations number
3
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Journal of graph theory → ACNP
ISSN journal
03649024
Volume
17
Issue
5
Year of publication
1993
Pages
629 - 631
Database
ISI
SICI code
0364-9024(1993)17:5<629:ANOMTG>2.0.ZU;2-6
Abstract
We show that a maximal triangle-free graph on n vertices with minimum degree delta contains an independent set of 3delta - n vertices which have identical neighborhoods. This yields a simple proof that if the b inding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. (C) 1993 John Wiley & Sons, Inc .