Independence, odd girth, and average degree

Löwenstein, Christian; Pedersen, Anders Sune; Rautenbach, Dieter GND; Regen, Friedrich GND

We prove several best-possible lower bounds in terms of the order and the average degree for the independence number of graphs which 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 $3$ due to Heckman and Thomas [A New Proof of the Independence Ratio of Triangle-Free Cubic Graphs, {\it Discrete Math.} {\bf 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$.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved