Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649991 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
We prove that a K4K4-free graph GG of order nn, size mm and maximum degree at most three has an independent set of cardinality at least 17(4n−m−λ−tr), where λλ counts the number of components of GG 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 GG. 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].
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jochen Harant, Michael A. Henning, Dieter Rautenbach, Ingo Schiermeyer,