@string{ipl = "Information Processing Letters"}
@string{tcs = "Theoretical Computer Science"}
@string{structures96 = "Proceedings of the 11th Annual IEEE Conference on
Computational Complexity"}
@String{adm = "Annals of Discrete Mathematics"}
@String{nh = "North-Holland"}
@String{nha = "Amsterdam"}
@string{sigactnews = "SIGACT News"}
@article{bod-thi-yam:j:greedy-for-maximum-independent-sets,
Author = "H.~Bodlaender and D.~Thilikos and K.~Yamazaki",
Title = "It is hard to Know when Greedy is good for Finding Independent Sets",
Journal = ipl,
Year = "1997",
Volume = "61",
Pages = "101--106"
}
@inproceedings{fei-kil:c:chromatic-number,
Title = "Zero Knowledge and the Chromatic Number",
Author = "U.~Feige and J.~Kilian",
Booktitle = structures96,
pages={278--287},
year={1996},
Publisher = "IEEE Computer Society Press"
}
@book{gar-joh:b:int,
Author = "M.~Garey and D.~Johnson",
Title = "Computers
and Intractability: A Guide to the Theory of NP-Completeness",
address="New York",
Publisher = "{W. H. Freeman}",
Year = "1979"
}
@article{gar-joh-sto:j:simplified-np-completeness,
Author = "M.~Garey and D.~Johnson and L.~Stockmeyer",
Title = "Some Simplified {N}{P}-Complete Graph Problems",
Journal = tcs,
Year = "1976",
Volume = "1",
Pages = "237--267"
}
@incollection{gro-lov-sch:b:perfect-graphs,
author = "M.~Gr{\"o}tschel and L.~Lov{\'a}sz and
A.~Schrijver",
title = "Polynomial Algorithms for Perfect Graphs",
booktitle = "Perfect Graphs",
publisher = nh,
year = "1984",
volume = "21",
series = adm,
address = nha,
pages = "325--356"
}
@article{hem-rot:j:max-independent-set-by-greed,
Author = "E.~Hemaspaandra and J.~Rothe",
Title = "Recognizing When Greed Can Approximate Maximum Independent Sets is
Complete for Parallel Access to {NP}",
Journal = ipl,
Year = "1998",
Month = "February",
Volume = "65",
Number = "3",
Pages = "151--156",
}
@inproceedings{joh:c:graph-coloring,
author={D.~Johnson},
title={Worst
Case Behavior of Graph Coloring Algorithms},
booktitle={Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing},
year={1974},
publisher="Utilitas Mathematica Publishing",
month={February/March},
pages={513-527},
summary = {heuristics for variety of problems; superceded by joh:c:graph-coloring}
}
@incollection{mat-mar-isa:b:graph-coloring,
Author = {D.~Matula and G.~Marble and J.~Isaacson},
Title = {Graph
Coloring Algorithms},
Booktitle = "Graph Theory and Computing",
Publisher = "Academic Press",
address="New York",
Editor = "R.~Read",
year={1972},
pages={109--122}
}
@article{sto:j:planar-3color,
Author = "L. Stockmeyer",
Title = "Planar 3-Colorability is {N}{P}-complete",
Journal = sigactnews,
year="1973",
volume={5},
number={3},
pages={19--25}
}
@article{woo:j:graph-coloring,
author={D.~Wood},
title={A Technique for Coloring a Graph Applicable to Large Scale
Time-Tabling Problems},
journal={The Computer Journal},
volume={12},
year={1969},
pages={317--319}
}