2-FACTORS IN TRIANGLE-FREE GRAPHS

Authors
BAUER D VANDENHEUVEL J SCHMEICHEL E
Citation
D. Bauer et al., 2-FACTORS IN TRIANGLE-FREE GRAPHS, Journal of graph theory, 21(4), 1996, pp. 405-412
Citations number
14
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Journal of graph theory → ACNP
ISSN journal
03649024
Volume
21
Issue
4
Year of publication
1996
Pages
405 - 412
Database
ISI
SICI code
0364-9024(1996)21:4<405:2ITG>2.0.ZU;2-F
Abstract
We study the cycle structure of 1-tough, triangle-free graphs. In part icular, we prove that every such graph on n greater than or equal to 3 vertices with minimum degree delta greater than or equal to 1/4(n + 2 ) has a 2-factor. We also show this is best possible by exhibiting an infinite class of 1-tough, triangle-free graphs having delta = 1/4(n 1) and no 2-factor. (C) 1996 John Wiley & Sons, Inc.