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