Lower bounds on the independence number of certain graphs of odd girth at least seven

A. S. Pedersen, D. Rautenbach, F. Regen

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
Originalsprog Engelsk Discrete Applied Mathematics 159 2-3 143-151 9 0166-218X https://doi.org/10.1016/j.dam.2010.10.011 Udgivet - 2011

Citer dette

Pedersen, A. S. ; Rautenbach, D. ; Regen, F. / Lower bounds on the independence number of certain graphs of odd girth at least seven. I: Discrete Applied Mathematics. 2011 ; Bind 159, Nr. 2-3. s. 143-151.
@article{0582fc33029b4a0db12c2c2a9e41299f,
title = "Lower bounds on the independence number of certain graphs of odd girth at least seven",
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 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.",
author = "Pedersen, {A. S.} and D. Rautenbach and F. Regen",
year = "2011",
doi = "10.1016/j.dam.2010.10.011",
language = "English",
volume = "159",
pages = "143--151",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "2-3",

}

Lower bounds on the independence number of certain graphs of odd girth at least seven. / Pedersen, A. S.; Rautenbach, D.; Regen, F.

I: Discrete Applied Mathematics, Bind 159, Nr. 2-3, 2011, s. 143-151.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Lower bounds on the independence number of certain graphs of odd girth at least seven

AU - Pedersen, A. S.

AU - Rautenbach, D.

AU - Regen, F.

PY - 2011

Y1 - 2011

N2 - 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.

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.

U2 - 10.1016/j.dam.2010.10.011

DO - 10.1016/j.dam.2010.10.011

M3 - Journal article

VL - 159

SP - 143

EP - 151

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 2-3

ER -