The independence number in graphs of maximum degree three

Harant, Jochen GND; Henning, Michael A.; Rautenbach, Dieter GND; Schiermeyer, Ingo GND

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).


Citation style:
Harant, J., Henning, M.A., Rautenbach, D., Schiermeyer, I., 2007. The independence number in graphs of maximum degree three.
Could not load citation form. Default citation form is displayed.


Use and reproduction:
All rights reserved