# Independent set size of a large girth graphs

For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true

Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8d}\log_2d.$$

Where $n(G)$ is the vertex size of the graph, $d$ is the avg degree and $\alpha(G)$ is the size of maximum independent set.

My Question : Are there extensions of above result for graphs with girth $\geq l$ ?

• "square-free" graphs are not the same as girth >= 5 graphs. Your title says "square-free" but your question does not. Perhaps change your title to reflect this? – JimN Apr 17 '14 at 7:08
• yes. I will do it. – Vivek Bagaria Apr 17 '14 at 7:35

Bollobas showed that for any $d$ and any $g$, there exists a $d$-regular graph $G$ of girth at least $g$ such that
$$\alpha(G) < \frac{2n\log d}{d}.$$