Independence,odd girth,and average degree |
| |
Authors: | Christian Löwenstein Anders Sune Pedersen Dieter Rautenbach Friedrich Regen |
| |
Institution: | 1. Institut für Mathematik, TU Ilmenau Postfach 100565, D‐98684 Ilmenau, Germany;2. Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55 DK‐5230 Odense M, Denmark |
| |
Abstract: | We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m, our result implies the existence of an independent set of order at least (4n?m?1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011 |
| |
Keywords: | independence stability triangle‐free graph odd girth |
|
|