Article ID Journal Published Year Pages File Type
4650539 Discrete Mathematics 2008 11 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,