# An improved algorithm for approximating the chromatic number of G_{n,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 G_{n,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.