| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428288 | Information Processing Letters | 2006 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
