ALGORITHMS FOR APPROXIMATE GRAPH COLORING
Avrim L. Blum · DSpace@MIT (Massachusetts Institute of Technology) · 1991
A coloring of a graph is an assignment of colors to the vertices so that no two adjacent vertices are given the same color.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 2' .3. This thesis explores the approximation problem of coloring k-colorable graphs with as few additional colors as possible in polynomial time, focusing on the case of k = 3.For the worst-case problem, the previous best upper bound on the number of colors needed for coloring 3-colorable n-vertex graphs in polynomial time is O( .Jii,/ ./fogri,)colors by Berger and Rompel, improving a bound of 0( .Jii,) colors by Wigderson.We present I would like to thank first of all my advisor Ron Rivest for his encouragement and his help, and for his always good sense of worthwhile research directions to explore.Both at a high level and at a detailed level, he has helped me throughout my graduate student years with his suggestions, ideas, and his ability to draw intuition from a wide variety of research areas.Portions of this thesis are based on joint work with Joel Spencer.I would like to thank Joel for all he has taught me, for attempting to impart to me some of his probabilistic intuition, and for many exciting discussions.