Improving the performance guarantee for approximate graph coloring

The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it uses on the input graph and the chromauc number of this graph. The previous best known polynomial-time algorithm had a performance guarantee O(n/logn) for graphs on n vertices. This result stood unchallenged for eight years. This paper presents an efficient algorithm with performance guarantee of O(n(loglog n)2/(logn)2).