Selected papers that cite this one
- N. Alon, P. Kelsen, S. Mahajan, and H. Ramesh. Approximate Hypergraph Coloring Nordic Journal of Computing, 3(4):425-439, Winter 1996.
- Avrim Blum and David Karger. An \tilde{O}(n^{3/14})-coloring algorithm for 3-colorable graphs. Information Processing Letters, 61(1):49-53, 14 January 1997.
- L. J. Cowen, W. Goddard, and C. E. Jesurum. Coloring with defect. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 548-557, New Orleans, Louisiana, 5-7 January 1997.
- Marc Demange, Pascal Grisoni, and Vangelis Th. Paschos. Differential approximation algorithms for some combinatorial optimization problems. Theoretical Computer Science, 209(1-2):107-122, 6 December 1998.
- Uriel Feige. Randomized graph products, chromatic numbers, and the Lovasz theta-function (extended abstract). In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 635-640, Las Vegas, Nevada, 29 May-1 June 1995.
- Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. Efficient learning of typical finite automata from random walks. Information and Computation, 138(1):23-48, 10 October 1997.
- David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246-265, March 1998.
Selected references
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Avrim Blum. An \tilde{O}(n^{0.4})-approximation algorithm for 3-coloring (and improved approximation algorithm for k-coloring). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 535-542, Seattle, Washington, 15-17 May 1989.
- Avrim Blum. Some tools for approximate 3-coloring (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 554-562, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 286-293, San Diego, California, 16-18 May 1993.
- Sundar Vishwanathan. Randomized online graph coloring (preliminary version). In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 464-469, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, October 1983.