NEW APPROXIMATION ALGORITHMS FOR GRAPH-COLORING

The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k greater-than-or-equal-to 3. This paper explores the approximation problem of coloring k-colorable graphs with as few additional colors as possible in polynomial time, with special focus on the case of k = 3. The previous best upper bound on the number of colors needed for coloring 3-colorable n-vertex graphs in polynomial time was O(square-root n/square-root log n) colors by Berger and Rompel, improving a bound of O(square-root n) colors by Wigderson. This paper presents an algorithm to color any 3-colorable graph with O(n3/8 polylog(n)) colors, thus breaking an ''O((n1/2-o(1)) barrier''. The algorithm given here is based on examining second-order neighborhoods of vertices, rather than just immediate neighborhoods of vertices as in previous approaches. We extend our results to improve the worst-case bounds for coloring k-colorable graphs for constant k > 3 as well.