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/ log n ). 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.

Authors

• Avi Wigderson

Keywords

No keywords are indexed for this paper.