×

Improving the performance guarantee for approximate graph coloring. (English) Zbl 0627.68057

The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it uses on the input graph and the chromatic number of this graph. The previous best known polynomial-time algorithm had a performance guarantee O(n/log n) for graphs on n vertices. This result stood unchallenged for eight years. This paper presents an efficient algorithm with performance guarantee of O(n(log log n)\({}^ 2/(\log n)^ 2)\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI