A new approximate graph coloring algorithm

Let A be a graph coloring algorithm. Denote by À (G) the ratio between the maximum number of colors A will use to color the graph G, and the chromatic number of G,x(G). For most existing polynomial coloring algorithms, À(G) can be as bad as O(n), where n is the number of vertices in G. The best currently known algorithm guarantees À (G)=O(n/logn). In this paper we present a simple and efficient coloring algorithm which guarantees À(G)≤x(G)n (equation), a considerable improvemėnt over the current bounds.