Abstract
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 frac(1, 7) (4 n - m - λ - t r), where λ 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 [C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math. 233 (2001) 233-237].
Original language | English |
---|---|
Pages (from-to) | 5829-5833 |
Number of pages | 5 |
Journal | Discrete Mathematics |
Volume | 308 |
Issue number | 23 |
DOIs | |
Publication status | Published - 6 Dec 2008 |
Externally published | Yes |
Keywords
- Cubic graph
- Independence
- Triangle
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics