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$ ?

  • $\begingroup$ "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? $\endgroup$
    – JimN
    Apr 17, 2014 at 7:08
  • $\begingroup$ yes. I will do it. $\endgroup$ Apr 17, 2014 at 7:35

1 Answer 1


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}. $$

So you cannot hope for more than a factor 16 improvement. McKay gave somewhat sharper bounds.

  • $\begingroup$ Are there any mild conditions which can be assumed to get a better bound for graphs with high girth? $\endgroup$ Apr 16, 2014 at 5:57
  • $\begingroup$ @Bagaria I am not aware of any. But I do not know the literature on the question very well. McKay's paper is concerned with getting exact bounds. It might be worth going into the probabilistic constructions which give the bounds. $\endgroup$ Apr 16, 2014 at 20:02
  • $\begingroup$ I have read above the paper by Bollobas and almost understood the proof. But, I am not able to understand the crux of the proof, which part of the proof is the most essential? Once that is understood, one could probably add a relevant constraint and improve the bound. $\endgroup$ Apr 27, 2014 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.