An improved algorithm for approximating the chromatic number of Gn,p

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 in polynomial expected time. The algorithm applies to edge probabilities c0/n⩽p⩽0.99, where c0>0 is a certain constant.