An improved algorithm for approximating the chromatic number of Gn,p
Amin Coja-Oghlan and Lars Kuhtz
Answering a question of Krivelevich and Vu [M. Krivelevich, V.H. Vu, Approximating the independence number and the chromatic number in expected polynomial time, J. Combin. Optimization 6 (2002) 143–155], we present an algorithm for approximating the chromatic number of random graphs Gn,p within a factor of O(\sqrt{np/\ln(np)}) in polynomial expected time. The algorithm applies to edge probabilities c_0 \leq p \leq 0.99, where c_0 > 0 is a certain constant.
Information Processing Letters, volume 99, issue 6, 30 September 2006, pages 234-238.