Some Famous Papers for Graph Coloring

9. E. Halperin, R. Nathaniel and U. Zwick, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 319-326, 2001.
Coloring k-colorable Graphs Using Small Palettes

8. N. Alon and N. Kahale, Mathematical Programming, 80:253-264, 1998.
Approximating the independence number via the theta-function

7. A. Blum and D. Karger, Information Processing Letters, 61:49-53, 1997.
An O(n ^(3/14))-coloring Algorithm for 3-colorable Graphs

6. D. Karger, R. Motwani and M. Sudan, Journal of the ACM, 45:246-265, 1998.
Approximate Graph Coloring by Semidefinite Programming

5. A. Blum, Journal of the ACM, 41:470-516, 1994.
New Approximation Algorithms for Graph Coloring

4. M. M. Halldorsson, 45:19-23, 1993.
A Still Better Performance Guarantee for Approximate Graph Coloring

3. R. Boppana and M. M. Hallorsson, BIT, 32:180-196, 1992.
Approximating Maximum Independent Sets by Excluding Subgraphs

2. B. Berger and J. Rompel, Algorithmica, 5(4):449-466, 1990.
A Better Performance Guarantee for Approximate Graph Coloring

1. A. Wigderson, Information Processing Letters, 30:729-735, 1983.
Improving the Performance Guarantee for Approximate Graph Coloring