Wigderson, Avi Improving the performance guarantee for approximate graph coloring. (English) Zbl 0627.68057 J. Assoc. Comput. Mach. 30, 729-735 (1983). 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)\). Cited in 1 ReviewCited in 36 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs Keywords:NP-completeness; performance guarantee of a graph coloring algorithm; number of colors; chromatic number PDFBibTeX XMLCite \textit{A. Wigderson}, J. Assoc. Comput. Mach. 30, 729--735 (1983; Zbl 0627.68057) Full Text: DOI