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

### Zitieren

Zitierform:

Harant, Jochen / Henning, Michael A. / Rautenbach, Dieter / et al: The independence number in graphs of maximum degree three. 2007.

### Zugriffsstatistik

Gesamt:
Volltextzugriffe: