Treffer: Approximating maximum independent set in k-clique-free graphs.

In this paper we study lower bounds and approximation algorithms for the independence number α(G) in k-clique-free graphs G. Ajtai et al. [1] showed that there exists an absolute constant c1 such that for any k-clique-free graph G on n vertices and with average degree ¯d, α(G) ≥ c1 log((log ¯d)/k)/dn We improve this lower bound for α(G) as follows: Let G be a connected k-clique-free graph on n vertices with maximum degree δ(G) ≤ n − 2. Then α(G) ≥ n(¯d(k − 2)2 log(¯d(k − 2)2) − ¯d(k − 2)2 + 1)/(¯d(k − 2)2 − 1)2 for ¯d ≥ 2. For graphs with moderate maximum degree Halldórsson and J. Radhakrishnan For graphs with moderate to large values of δ Halldórsson and J. Radhakrishnan [ABSTRACT FROM AUTHOR]