Approximation Algorithm for 3-Coloring

This paper presents a polynomial-time algorithm to color any 3-colorable n-node graph with O(n2i5 10g”~ n) colors, improving the best previously known bound of O(fi/m colors. By reducing the number of colors needed to color a S-colorable graph, the algo- rithm also improves the bound for k-coloring for fixed X: 2 3 from the previous O((n/logn)‘-‘I(‘-‘)) colors to

O(n1-1/(“-4/3)log8/5 n) colors. An extension of the algorithm further improves the bounds. Precise values appear in a table at, the end of this paper. 1 Introduction A k-coloring of a graph is a mapping of CE distinct col- ors to the nodes of the graph such that no two adjacent nodes receive the same color. Wigderson [W], as part of an approximation algorithm for graph coloring for gen- eral k, gave a simple algorithm to color any J-colorable graph with O(J) 1 n co ors. Recently, several researchers: Berger and Rompel [BR], Linial, Saks, and Wigderson [LSW], and Raghavan [R] independently have improved this bound to 0(,/Z/m. The techniques in these algorithms, however, do not, seem useful for improving the bound significantly further, and even O(fi/ log2 n) colors appears completely out of reach. The difficulty in improving these results has motivated the work of Linial and Vazirani [LV] in which evidence for an n’ lower bound for the general chromatic number approx- imation problem is given. We present an algorithm that uses a quite different strategy from the other approximation algorithms and *The d notation, in which log’ n factors are ignored, is bor- rowed from E. Luks’s talk...

Website: www.cse.iitk.ac.in | Filesize: -
No of Page(s): 8
Download An &I'**)-Approximation Algorithm for 3-Coloring*.pdf