0
$\begingroup$

Notations used

  1. $\alpha(G) = $ Max sized independent set of graph $G$.
  2. $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!

$\endgroup$
3
  • $\begingroup$ In paper (arxiv.org/pdf/math.CO/0404325), paragraph above lemma 6 claims that following theorem is proved in Random Graphs, 1st edition by Bollobas. Sadly, I have only the 2nd edition of the book and I am not able to find its proof in the 2nd edition. $\endgroup$ Oct 31, 2013 at 12:18
  • $\begingroup$ This may contain it: sciencedirect.com/science/article/pii/0095895691900804 $\endgroup$ Oct 31, 2013 at 20:39
  • $\begingroup$ @PéterKomjáth: The above link doesn't deal with graphs with few triangles. $\endgroup$ Nov 1, 2013 at 11:20

0

Your Answer

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