摘要: This paper presents a polynomial-time algorithm to color any 3-colorable n-node graph with O(n2/5 log8/5n) colors, improving the best previously known bound of O(√n/√logn) colors. By reducing number colors needed graph, also improves for k-coloring fixed k ≥ 3 from previous O((n/log n)1-1/(k-1)) O(n1-1/(k-4/3) An extension further bounds. Precise values appear in table at end this paper.
acm.org
sci-hub.se 参考文章(3)
Avi Wigderson, Improving the performance guarantee for approximate graph coloring Journal of the ACM. ,vol. 30, pp. 729- 735 ,(1983) , 10.1145/2157.2158
Burkhard Monien, Ewald Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem Acta Informatica. ,vol. 22, pp. 115- 123 ,(1985) , 10.1007/BF00290149
Bonnie Berger, John Rompel, A better performance guarantee for approximate graph coloring Algorithmica. ,vol. 5, pp. 459- 466 ,(1990) , 10.1007/BF01840398