@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}
	}