[AN05]	D. Achlioptas, A. Naor (2005). The Two Possible Values of the Chromatic Number of a Random Graph. To appear in Annals of Mathematics. [ bib ]
[COT04]	A. Coja-Oghlan, A. Taraz (2004). Exact and approximative algorithms for coloring G(n, p). Random structures & algorithms, vol. 24, no. 3, pp. 259-278. [ bib | DOI ]
[CV04]	P. Crescenzi, K. Viggo (2004). A compendium of NP optimization problems. Available online (last visited February 2005). [ bib | .html ]
[GRS03]	C. Gomes, R. Regis, D. Shmoys (2003). An Improved Approximation for the Partial Latin Square Extension Problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Baltimore, Maryland, USA. [ bib ]
[Pas03]	V. T. Paschos (2003). Polynomial approximation and graph-coloring. Computing, vol. 70, no. 1, pp. 41-86. [ bib | DOI ]
[BGS98]	M. Bellare, O. Goldreich, M. Sudan (1998). Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM Journal on Computing, vol. 27, no. 3, pp. 804-915. [ bib | DOI ]
[FK98]	U. Feige, J. Kilian (1998). Zero Knowledge and the Chromatic Number. Journal of Computer and System Sciences, vol. 57, no. 2, pp. 187-199. [ bib ]
[Hal93]	M. M. Halldórsson (1993). A still better performance guarantee for approximate graph coloring. Information Processing Letters, vol. 45, no. 1, pp. 19-23. [ bib | DOI ]
[BR90]	B. Berger, J. Rompel (1990). A better performance guarantee for approximate graph colouring. Algorithmica, vol. 5, no. 4, pp. 459-466. [ bib ]
[Wig83]	A. Wigderson (1983). Improving the performance guarantee for approximate graph coloring. Journal of the ACM, vol. 30, no. 4, pp. 729-735. [ bib | DOI ]
[Wig82]	A. Wigderson (1982). A new approximate graph coloring algorithm. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 325-329. [ bib ]
[Joh74]	D. S. Johnson (1974). Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, vol. 9, pp. 256-278. [ bib ]