Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418611 | Discrete Applied Mathematics | 2011 | 9 Pages |
Abstract
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] proved that every connected subcubic triangle-free graph GG has an independent set of order at least (4n(G)−m(G)−1)/7(4n(G)−m(G)−1)/7 where n(G)n(G) and m(G)m(G) denote the order and size of GG, respectively. We conjecture that every connected subcubic graph GG of odd girth at least seven has an independent set of order at least (5n(G)−m(G)−1)/9(5n(G)−m(G)−1)/9 and verify our conjecture under some additional technical assumptions.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anders Sune Pedersen, Dieter Rautenbach, Friedrich Regen,