An improved algorithm for approximating the chromatic number of G(n,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 G(n.p) within a factor of O(root np/1n(np)) in polynomial expected time. The algorithm applies to edge probabilities c0/n   0 is a certain constant. (c) 2006 Elsevier B.V. All rights reserved.
approximation algorithms graph algorithms