[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 ]
|