### Abstract

Original language | English |
---|---|

Journal | Discrete Applied Mathematics |

Volume | 159 |

Issue number | 2-3 |

Pages (from-to) | 143-151 |

Number of pages | 9 |

ISSN | 0166-218X |

DOIs | |

Publication status | Published - 2011 |

### Cite this

*Discrete Applied Mathematics*,

*159*(2-3), 143-151. https://doi.org/10.1016/j.dam.2010.10.011

}

*Discrete Applied Mathematics*, vol. 159, no. 2-3, pp. 143-151. https://doi.org/10.1016/j.dam.2010.10.011

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

Research output: Contribution to journal › Journal article › Research › peer-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 -