Notations used
- $\alpha(G) = $ Max sized independent set of graph $G$.
- $n(G) = $ Number of vertex in graph $G$.
Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$,
$$\alpha(G) \geq \frac{n(G)}{8\Delta}\log_2\Delta.$$
For a general graph, $\alpha(G) \geq n(G)/(\Delta+1)$, hence the above result is an improvement by a factor of $O(\log_2\Delta)$. The proof of the above theorem is heavily uses the triangle-free property of the graph.
Theorem : For a graph $G$ having maximum degree $\Delta$ and having at most T triangles, $$\alpha(G) \geq \frac{n(G)}{10\Delta}\Bigg(\log_2\Delta - \frac{1}{2}\log_2\Big(\frac{T}{n(G)}\Big)\Bigg)$$
I am not able to find the proof for the above theorem. It would be great if someone could point me to a book or paper which proves the above theorem
Thanks in advance!