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 '14 at 7:08
  • $\begingroup$ yes. I will do it. $\endgroup$ – 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}. $$

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

| cite | improve this answer | |
  • $\begingroup$ Are there any mild conditions which can be assumed to get a better bound for graphs with high girth? $\endgroup$ – Vivek Bagaria Apr 16 '14 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$ – Sasho Nikolov Apr 16 '14 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$ – Vivek Bagaria Apr 27 '14 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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