TY - JOUR
TI - Lower bounds on the independence number of certain graphs of odd girth at least seven
LA - eng
AU - Pedersen, A. S.
AU - Rautenbach, D.
AU - Regen, F.
JF - Discrete Applied Mathematics
VL - 159
IS - 2-3
SP - 143
EP - 151
PY - 2011
SN - 18726771, 0166218x
AB - 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 G has an independent set of order at least (4n(G) - m(G) - 1)/7 where n(G) and m(G) denote the order and size of G, respectively. We conjecture that every connected subcubic graph G of odd girth at least seven has an independent set of order at least (5n(G) - m(G) - 1)/9 and verify our conjecture under some additional technical assumptions. (C) 2010 Elsevier B.V. All rights reserved.
DO - 10.1016/j.dam.2010.10.011
ER -