The independence number in graphs of maximum degree three
We prove that a K4-free graph G of order n, size m and maximum degree at most three has an independent set of cardinality at least 1/7 (4n − m − \lambda − tr) where \lambda counts the number of components of G whose blocks are each either isomorphic to one of four specific graphs or edges between two of these four specific graphs and tr is the maximum number of vertex-disjoint triangles in G. Our result generalizes a bound due to Heckman and Thomas (A New Proof of the Independence Ratio of Triangle-Free Cubic Graphs, Discrete Math. 233 (2001), 233-237).
Use and reproduction:
All rights reserved