New approximation algorithms for graph coloring

Publisher Website
Google Scholar
Abstract
The problem of coloring a graph with the minimum number of colorsis well known to be NP-hard, even restricted tok-colorable graphs for constantk ≥ 3. This paper explores theapproximation problem of coloringk-colorable graphs with as fewadditional colors as possible in polynomial time, with special focus onthe case of k = 3.The previous best upper bound on the number of colors needed forcoloring 3-colorable n-vertex graphsin polynomial time was on/logn colors by Berger and Rompel, improving a bound ofon colors by Wigderson. This paper presents an algorithmto color any 3-colorable graph with on3/8polylogn colors, thus breaking an“O((n1/2-&ogr;(1))barrier”. The algorithm given here is based on examiningsecond-order neighborhoods of vertices, rather than just immediateneighborhoods of vertices as in previous approaches. We extend ourresults to improve the worst-case bounds for coloringk-colorable graphs for constantk 3 as well.