### Abstract

Let G be a d-regular graph with girth g, and let α be the independence number of G. We show that α (G) ≥ frac(1, 2) (1 - (d - 1)^{- 2 / (d - 2)} - ε{lunate} (g)) n where ε{lunate} (g) → 0 as g → ∞, and we compute explicit bounds on ε{lunate} (g) for small g. For large g this improves previous results for all d ≥ 7. The method is by analysis of a simple greedy algorithm which was motivated by the differential equation method used to bound independent set sizes in random regular graphs. We use a "nibble" type of approach but require none of the sophistication of the usual nibble method arguments, relying only upon a difference equation for the expected values of certain random variables. The difference equation is approximated by a differential equation.

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

Pages (from-to) | 999-1009 |

Number of pages | 11 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 97 |

Issue number | 6 |

DOIs | |

Publication status | Published - Nov 2007 |

Externally published | Yes |

### Keywords

- Differential equation
- Graph
- Independence ratio
- Independent set
- Large girth

## Cite this

*Journal of Combinatorial Theory, Series B*,

*97*(6), 999-1009. https://doi.org/10.1016/j.jctb.2007.02.006