Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650539 | Discrete Mathematics | 2008 | 11 Pages |
In 1979, Staton proved that every triangle-free graph GG with maximum degree at most three has an independent set with size at least 514 of the number of vertices of GG. Fraughnaugh [size and independence in triangle-free graphs with maximum degree three, J. Graph Theory 14 (5) (1990) 525–535] and Heckman and Thomas [A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math 233 (2001) 233–237] provided shorter proofs of the same result. An analysis of the cases of equality for the main results in the last paper is presented. Also, a proof that there are only two connected triangle-free graphs with maximum degree at most three and independence ratio 514 is given; it is self-contained and does not require a computer search.