@book{AaKo89,
   author = {E.H.L. Aarts and J.H.M Korst},
   address = {Chichester, U.K.},
   publisher = {John Wiley \& Sons},
   title = {Simulated Annealing and Boltzmann Machines},
   year = {1989},
   annote = {Book providing an overview of simulated annealing techniques and issues.}
}

@article{DyFr89,
   author = {M. Dyer and A. Frieze},
   journal = {Journal of Algorithms},
   pages = {451--489},
   title = {The solution of some random NP--Hard problems in polynomial expected time},
   volume = {10},
   year = {1989},
   annote = {Explores the possibility of coloring random $k$--colorable graphs in polynomial time.}
}

@article{Ku89,
   author = {Ludek Ku{\v c}era},
   journal = {Information Processing Letters},
   pages = {233--236},
   title = {Graphs with small chromatic numbers are easy to color},
   volume = {30},
   year = {1989},
   annote = {This paper extends the result of \cite{Tu88} on coloring $(1-\epsilon)\log n$--colorable graphs to $o(\sqrt{n/\log n})$--colorable graphs.}
}

@article{Ku91,
   author = {Ludek Ku{\v c}era},
   journal = {Journal of Algorithms},
   pages = {674--684},
   title = {The greedy coloring is a bad probabilistic algorithm},
   volume = {12},
   year = {1991},
   annote = {Shows that a natural randomization of the greedy coloring is bad by giving a $O(n^\epsilon)$--colorable random graph that is colored by the greedy algorithm using almost surely at least $\Omega(n/\log n)$ colors.}
}

@inproceedings{Ku77,
   author = {Ludek Ku{\v c}era},
   address = {Berlin},
   booktitle = {Foundations of Comupation Theory 77},
   editor = {M. Karpinski},
   pages = {447--451},
   publisher = {Springer},
   series = {Lecture Notes in Computer Science},
   title = {Expected behavior of graph coloring algorithms},
   volume = {56},
   year = {1977}
}

@article{Bo,
   author = {B. Bollob\'as},
   journal = {Combinatorica},
   pages = {49--56},
   title = {The Chromatic Number of Random Graphs},
   volume = {8},
   year = {???}
}

@inproceedings{MaKu90,
   author = {David Matula and Ludek Ku{\v c}era},
   booktitle = {Random Graphs'87},
   editor = {M. Karonski and J. Jaworski and A. Rucinski},
   pages = {175--187},
   publisher = {John Wiley and Sons},
   title = {An Expose--and--Merge Algorithm and the Chromatic Number of a Random Graph},
   year = {1990},
   annote = {Proves a bound on the chromatic number of a random graph $G(n,p)$ to be $(1+o(1)){n/2\log_{1\over {1-p} n }}$, as did  \cite{Bo}.}
}

@article{Ak73,
   author = {E.A. Akkoyunlu},
   journal = {SIAM Journal on Computing},
   number = {1},
   pages = {1--6},
   title = {The Enumeration of Maximal Cliques of Large Graphs},
   volume = {2},
   year = {1973},
   annote = {An implicit enumeration routine for listing all maximal cliques.}
}

@article{ApHa77a,
   author = {K. Appel and W. Haken},
   journal = {Illinois Journal of Mathematics},
   pages = {421--490},
   title = {Every planar map is 4-colorable -- 1: Discharging},
   volume = {21},
   year = {1977}
}

@article{ApHa77b,
   author = {K. Appel and W. Haken},
   journal = {Illinois Journal of Mathematics},
   pages = {491--567},
   title = {Every planar map is 4-colorable -- 2: Reducibility},
   volume = {21},
   year = {1977}
}

@inproceedings{ALMSS92,
   author = {S. Arora and C. Lund and R. Motwani and M. Sudan and M. Szegedy},
   address = {Los Angeles, CA},
   booktitle = {Proceedings 33rd {IEEE} {S}ymposium on the {F}oundations of {C}omputer {S}cience},
   pages = {14--23},
   publisher = {IEEE Computer Society},
   title = {Proof verification and hardness of approximation problems},
   year = {1992},
   annote = {Strengthens result of \cite{ArSa92}: there is an $\epsilon$ such that no polynomial-time heuristic for clique can be guaranteed to come within a factor of $n^\epsilon$ of optimal unless P = NP.}
}

@inproceedings{ArSa92,
   author = {S. Arora and S. Safra},
   address = {Los Angeles, CA},
   booktitle = {Proceedings 33rd {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience},
   pages = {2--13},
   publisher = {IEEE Computer Society},
   title = {Probabilistic checking of proofs; A new characterization of NP},
   year = {1992},
   annote = {Shows that no polynomial-time heuristic for clique can be guaranteed to come within a constant factor of optimal unless P = NP.}
}

@article{Ba91,
   author = {Luitpold Babel},
   journal = {Computing},
   pages = {321--341},
   title = {Finding Maximum Cliques in Arbitrary and in Special Graphs},
   volume = {46},
   year = {1991},
   annote = {Contains a branch and bound algorithm for maximum clique.  Analyzes when branch and bound tree has a polynomial number of nodes so gives a number of polynomially solvable special cases.  Bounds based on graph coloring.}
}

@article{BaSa77,
   author = {Egon Balas and H. Samuelsson},
   journal = {Naval Research Logistics Quarterly},
   number = {2},
   pages = {213--233},
   title = {A Node Covering Algorithm},
   volume = {24},
   year = {1977},
   annote = {A polyhedral approach to vertex packing.}
}

@article{BaXu91,
   author = {Egon Balas and Jue Xue},
   journal = {SIAM Journal on Computing},
   number = {2},
   pages = {209--221},
   title = {Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs},
   volume = {20},
   year = {1991},
   annote = {A branch and bound algorithm for maximum weighted cliques.  This work is a generalization of \cite{BaYu86}.  The algorithm is based on a method for finding weighted colorings of triangulated graphs.
}
}

@article{BaYu86,
   author = {Egon Balas and Chang Sung Yu},
   journal = {SIAM Journal on Computing},
   number = {4},
   pages = {1054--1068},
   title = {Finding a Maximum Clique in an Arbitrary Graph},
   volume = {15},
   year = {1986},
   annote = {A branch and bound procedure for maximum clique.  Based on coloring triangulated graphs.  Computational experiments.}
}

@book{BaGu91,
   author = {Jean--Pierre Barth\'elemy and Alain Gu\'enoche},
   address = {New York, NY},
   publisher = {John Wiley and Sons},
   title = {Trees and Proximity Representations},
   year = {1991},
   annote = {Chapter 5 contains an application for clique.  A set of items (biological species, archeological artifacts) need to be classified into a tree.  A distance is found between all items.  If the resulting distance is a tree distance, then that is the tree.  Otherwise, form a graph where each node is a partition and two nodes are connected if they are tree--compatible (an inclusion relation).  The only partitions permitted are those that represent a cut in the distance metric.  A clique is a set of partitions that is compatible with a tree.}
}

@article{BeRo90,
   author = {B. Berger and J. Rompel},
   journal = {Algorithmica},
   pages = {459--466},
   title = {A Better Permance Guarantee for Approximate Graph Coloring},
   volume = {5},
   year = {1990},
   annote = {Construction for graph coloring that in the worst case uses $O(n(\log\log n/\log n)^3)$ times the optimal number of colors.}
}

@inproceedings{Bl89,
   author = {A. Blum},
   address = {New York},
   booktitle = {Proceedings 21st {ACM} {S}ymposium on {T}heory of {C}omputing},
   pages = {535--542},
   publisher = {ACM},
   title = {An $\tilde{O} ( n^{0.4} )$-approximation algorithm for 3-coloring (and improved approximation algorithms for $k$-coloring)},
   year = {1989},
   annote = {See title.}
}

@inproceedings{Bl90,
   author = {A. Blum},
   address = {Los Angeles, CA},
   booktitle = {Proceedings 31st {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience},
   pages = {554--562},
   publisher = {IEEE Computer Society},
   title = {Some tools for approximate 3-coloring},
   year = {1990},
   annote = {Shows that how to get an $n^.375$ coloring of a 3-colorable graph in polynomial time.  Also considers models of random 3-colorable graphs where 3-colorings can be efficiently found with high probabibity.}
}

@article{BoEr76,
   author = {B. Bollob\'as and P. Erd\"os},
   journal = {Mathematical Proceedings of the Cambride Philosophical Society},
   pages = {419--427},
   title = {Cliques in Random Graphs},
   volume = {80},
   year = {1976},
   annote = {In a random graph, the clique size is 2log n.}
}

@article{BoTh85,
   author = {B. Bollobas and A. Thomason},
   journal = {Annals of Discrete Math.},
   pages = {47--97},
   title = {Random graphs of small order},
   volume = {28},
   year = {1985},
   annote = {Discusses estimates of chromatic number and optimal clique size in random graphs and reports on an implementation of a variant of the coloring algorithm from \cite{JoMa82}.}
}

@article{Br79,
   author = {D. Br{\'e}laz},
   journal = {Communications of the ACM},
   pages = {251--256},
   title = {New Methods to Color Vertices of a Graph},
   volume = {22},
   year = {1979},
   annote = {Successive augmentation approach to graph coloring.  DSATUR chooses the vertex adjacent to the largest number of distinctly colored vertices.  Paper also discusses an implicit enumeration scheme for finding an optimal coloring using some of the principles of DSATUR to guide the search.}
}

@inproceedings{BCKT89,
   author = {P. Briggs and K. Cooper and K. Kennedy and L. Torczon},
   booktitle = {ASCM Conference on Program Language Design and Implementation},
   pages = {275--284},
   title = {Coloring Heuristics for Register Allocation},
   year = {1989}
}

@article{BrKe73,
   author = {Coen Bron and Joep Kerbosch},
   journal = {Communications of the ACM},
   number = {9},
   pages = {575--577},
   title = {Finding all Cliques of an Undirected Graph},
   volume = {16},
   year = {1973},
   annote = {An implicit enumeration algorithm for listing all cliques in a graph.  Includes easily translated code.}
}

@article{Br72,
   author = {R. J. Brown},
   journal = {Management Science},
   pages = {451--463},
   title = {Chromatic scheduling and the chromatic number problem},
   volume = {19},
   year = {1972},
   annote = {Implicit enumeration algorithm [not seen].}
}

@article{CaPa90,
   author = {R. Carraghan and P. M. Pardalos},
   journal = {Operations Research Letters},
   pages = {375--382},
   title = {An exact algorithm for the maximum clique problem},
   volume = {9},
   year = {1990},
   annote = {Implicit enumeration algorithm, designed to work well on sparse graphs.  Paper includes a program listing.}
}

@article{Ce85,
   author = {V. Cerny},
   journal = {Journal of Optimization Theory and Applications},
   pages = {41--51},
   title = {A Thermodynamical Approach to the Traveling Saleman Problem:  An Efficient Simulation Algorithm},
   volume = {45},
   year = {1985},
   annote = {With \cite{KGV83}, one of the two papers that first suggested the idea of simulated annealing, here applied to the traveling saleman problem.
}
}

@inproceedings{Ch82,
   author = {G.J. Chaitin},
   address = {New York, NY},
   booktitle = {Proceedings of the {ACM} {SIGPLAN} 82 Symposium on Compiler Construction},
   pages = {98--105},
   publisher = {ACM},
   title = {Register Allocation and Spilling via Graph Coloring},
   year = {1982},
   annote = {First (?) paper describing graph coloring and register allocation and graph coloring}
}

@article{CACCHM81,
   author = {G.J. Chaitin and M. Auslander and A.K. Chandra and J. Cocke and M.E. Hopkins and P. Markstein},
   journal = {Coputer Languages},
   pages = {47--57},
   title = {Register Allocation via Coloring},
   volume = {6},
   year = {1981},
   annote = {First to apply coloring approach to register allocation in an experimental compiler at IBM}
}

@article{CHD87,
   author = {M. Chams and A. Hertz and D. De Werra},
   journal = {European Journal of Operations Research},
   pages = {260--266},
   title = {Some Experiments with Simulated Annealing for Coloring Graphs},
   volume = {32},
   year = {1987},
   annote = {Simulated annealing applied to graph coloring.}
}

@inproceedings{ChHe84,
   author = {Fred C. Chow and John L. Hennessy},
   address = {New York, NY},
   booktitle = {Proceedings of the {ACM} {SIGPLAN} 84 Symposium on Compiler Construction},
   pages = {222--232},
   publisher = {ACM},
   title = {Register Allocation by Priority--based Coloring},
   year = {1984}
}

@article{ChHe90,
   author = {Fred C. Chow and John L. Hennessy},
   journal = {ACM Transactions on Programming Languages and Systems},
   number = {4},
   pages = {501--536},
   title = {The Priority--Based Coloring Approach to Register Allocation},
   volume = {12},
   year = {1990},
   annote = {A more extensive approach to register allocation that uses a number of different factors before applying a coloring heuristic.}
}

@article{Ch71,
   author = {N. Christofides},
   journal = {Computer Journal},
   pages = {38--39},
   title = {An algorithm for the chromatic number of a graph},
   volume = {14},
   year = {1971},
   annote = {Implicit enumeration algorithm [not seen].}
}

@book{Ch75,
   author = {N. Christofides},
   address = {London.},
   publisher = {Academic Press},
   title = {Graph Theory: An Algorithmic Approach},
   year = {1975},
   annote = {Contains an implicit enumeration algorithm, with a bug reported in \cite{KuJa85}.}
}

@article{CEG88,
   author = {N.E. Collins and R.W. Eglese and B.L. Golden},
   journal = {American Journal of Mathematical and Management Sciences},
   pages = {205--307},
   title = {Simulated Annealing:  An Annotated Bibliography},
   volume = {8},
   year = {1988},
   annote = {Very large and complete (circa 1988) bibliography of the state of simulated annealing.}
}

@article{CoGr73,
   author = {D. G. Corneil and B. Graham},
   journal = {SIAM Journal on Computing},
   pages = {311--218},
   title = {An algorithm for determining the chromatic number of a graph},
   volume = {2},
   year = {1973},
   annote = {Implicit enumeration algorithm based on Zykov's theorem.}
}

@article{De85,
   author = {De Werra, D.},
   journal = {European Journal of Operations Research},
   pages = {151--162},
   title = {An Introduction to Timetabling},
   volume = {19},
   year = {1985},
   annote = {A survey of techniques and papers for solving timetabling problems, including a section on graph coloring techniques.}
}

@inproceedings{FGLSS91,
   author = {U. Feige and S. Goldwasser and L. Lovasz and S. Safra and and M. Szegedy},
   address = {Los Angeles, CA},
   booktitle = {Proceedings 32nd {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience},
   pages = {2--12},
   publisher = {IEEE Computer Society},
   title = {Approximating clique is almost {NP}-Complete},
   year = {1991},
   annote = {First paper to show that no polynomial-time heuristic for clique can be guaranteed to come within a constant factor of optimal unless an unlikely conjecture held (in this case, NP contained in $P^{\log\log(n}$)).}
}

@article{FRS93,
   author = {T. A. Feo and M. G. C. Resende and S. H. Smith},
   journal = {Operations Research},
   pages = {(to appear)},
   title = {Greedy randomized adaptive search procedure for maximum independent set},
   year = {1993},
   annote = {Heuristic based on randomized search, somewhat on the principles suggested in \cite{JoMa82}.}
}

@inproceedings{FuSu92,
   author = {M. F\"{u}rer and C. R. Subramanian},
   address = {Berlin},
   booktitle = {Proceedings 3rd Scandinavian Workshop on Algorithmic Theory},
   publisher = {Springer Lecture Notes in Computer Science},
   title = {Coloring random graphs},
   year = {1992},
   annote = {Widens class of models for random $k$-colorably graphs for which
efficient $k$-coloring algorithms can be found.}
}

@article{Ga86,
   author = {Andreas Gamst},
   journal = {IEEE Transactions of Vehicular Echnology},
   number = {1},
   pages = {8--14},
   title = {Some Lower Bounds for a Class of Frequency Assignment Problems},
   volume = {35},
   year = {1986},
   annote = {An application for maximum weighted clique.  Lower bounds on the number of frequencies required for the assignment of frequencies to mobile radio telephone systems are found by finding large cliques in an associated graph.}
}

@article{GaJo76,
   author = {Michael R. Garey and David S. Johnson},
   journal = {Journal of the Association for Computing Machinery},
   pages = {43--49},
   title = {The Complexity of Near--Optimal Graph Coloring},
   volume = {23},
   year = {1976},
   annote = {Show that there exists no algorithm that colors a graph using within two times the optimal number of colors unless P=NP.}
}

@book{GaJo79,
   author = {Michael R. Garey and David S. Johnson},
   address = {San Francisco, CA},
   publisher = {W.H Freeman},
   title = {Computers and Instractability:  A Guide to the Theory of {NP}--Completeness},
   year = {1979},
   annote = {"The Bible."  An indispensible guide to NP--completeness and related issues.  Updated by Johnson's semiregular column in the Journal of Algorithms.}
}

@article{GJS76,
   author = {M. R. Garey and D. S. Johnson and H. C. So},
   journal = {IEEE Trans. on Circuits and Systems},
   pages = {591--599},
   title = {An Application of Graph Coloring To Printed Circuit Testing},
   volume = {CAS-23},
   year = {1976},
   annote = {Application mentioned in title yields interesting class of graphs for which heuristics are analyzed.}
}

@article{GeLi79,
   author = {L. Gerhards and W. Lindenberg},
   journal = {Computing},
   pages = {295--322},
   title = {Clique Detection for Nondirected Graphs:  Two New Algorithms},
   volume = {21},
   year = {1979},
   annote = {Two branch and bound algorithms for finding maximum clique are presented.
}
}

@article{Gl89,
   author = {Fred Glover},
   journal = {ORSA Journal on Computing},
   pages = {190--206},
   title = {Tabu Search, Part 1},
   volume = {1},
   year = {1989},
   annote = {A tutorial on tabu search for combinatorial optimization problems.}
}

@book{Go89,
   author = {D. E. Goldberg},
   address = {Reading, MA},
   publisher = {Addison-Wesley},
   title = {Genetic Algorithms in Search, Optimization \& Machine Learning},
   year = {1989},
   annote = {An introduction to genetic algorithms, although with nothing specifically about graph coloring or clique finding.}
}

@book{Go80,
   author = {M. Golumbic},
   address = {New York, NY},
   publisher = {Acadmeic Press},
   title = {Algorithmic Graph Theory and Perfect Graphs},
   year = {1980},
   annote = {A wonderful graph theory book with an emphasis on perfect graphs.
}
}

@article{GrMc75,
   author = {G.R. Grimmet and C.J.H. McDiarmid},
   journal = {Mathematical Proceedings of the Cambridge Philosophical Society},
   pages = {313--324},
   title = {On Colouring Random Graphs},
   volume = {77},
   year = {1975},
   annote = {Analysis of a simple successive approximation algorithm for coloring random graphs.}
}

@techreport{Ha90,
   author = {M. M. Halld\'orsson},
   address = {New Brunswick, NJl},
   institution = {DIMACS},
   number = {91--35},
   title = {A still better performance guarantee for approximate graph coloring},
   year = {1990},
   annote = {Heuristic for graph coloring that has current record for ``good'' worst-case behavior: $O(n(\log\log n)^2 /(\log n)^3$ times the optimal number of colors.}
}

@misc{HPV92,
   author = {J. Hasselberg and P. M. Pardalos and G. Vairaktarakis},
   howpublished = {Working paper, University of Florida},
   title = {Test case generators and computational results for the maximum clique problem},
   year = {1992},
   annote = {Generators from many applications.  Should be available
via anonymous FTP from DIMACS (in {\tt pub/challenge/graph/contributed/pardalos}).}
}

@article{HeDe87,
   author = {A. Hertz and De Werra, D.},
   journal = {Computing},
   pages = {345--351},
   title = {Using Tabu Search Techniques for Graph Coloring},
   volume = {39},
   year = {1987},
   annote = {A tabu search approach to graph coloring problems}
}

@article{Je92,
   author = {Mark Jerrum},
   journal = {Random Structures and Algorithms},
   number = {4},
   pages = {347--360},
   title = {Large Cliques Elude the Metropolis Process},
   volume = {3},
   year = {1992},
   annote = {This paper shows that simulated annealing needs exponential time to find a clique within a factor of 2 of the largest for random graphs.
}
}

@article{Jo74a,
   author = {David S. Johnson},
   journal = {Journal of Computer and System Sciences},
   pages = {256--278},
   title = {Approximation Algorithms for Combinatorial Problems},
   volume = {9},
   year = {1974},
   annote = {Introduced ``approximation algorithm'' terminology; includes
worst-case analysis of simple heuristics for clique and graph coloring.  The graph coloring results were extended in \cite{Jo74b}.}
}

@inproceedings{Jo74b,
   author = {David S. Johnson},
   address = {Winnipeg, Canada},
   booktitle = {Proceedings 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing},
   pages = {513--527},
   publisher = {Utilitas Mathematica Publishing},
   title = {Worst--Case Behavior og Graph Coloring Algorithms},
   year = {1974},
   annote = {Shows that a number of simple successive augmentation heuristics for graph coloring can do very poorly.}
}

@article{JAMS91,
   author = {David S. Johnson and Cecilia R. Aragon and Lyle A. McGeoch and Catherine Schevon},
   journal = {Operations Research},
   number = {3},
   pages = {378--406},
   title = {Optimization by Simulated Annealing:  An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning},
   volume = {39},
   year = {1991},
   annote = {A very thorough examination of the application of simulated annealing to graph coloring.  Examines randomly generated graphs and random "geometric" graphs.}
}

@techreport{JoMa82,
   author = {A. Johri and David W. Matula},
   address = {Dallas, Texas},
   institution = {Southern Methodist University},
   title = {Probabilistic Bounds and Heuristic Algorithms for Coloring Large Random Graphs},
   year = {1982}
}

@inproceedings{KRR89,
   author = {N. K. Karmarkar and K. G. Ramakrishnan and M. G. C. Resende},
   booktitle = {Proceedings of the XV Latin American Conference on Informatics I},
   pages = {241--260},
   title = {An interior point approach to the maximum independent set problem in dense random graphs},
   year = {1989},
   annote = {Interior point heuristics based on convex quadratic programming.}
}

@article{KGV83,
   author = {S. Kirkpatrick and C.D. Gelatt and M.P. Vecchi},
   journal = {Science},
   number = {13 May 1983},
   pages = {671--680},
   title = {Optimization by Simulated Annealing},
   volume = {220},
   year = {1983},
   annote = {First popular account of using simulated annealing for combinatorial optimization.}
}

@inproceedings{Ko79,
   author = {S. M. Korman},
   address = {New York},
   booktitle = {Combinatorial Optimization},
   editor = {N. Christofides and A. Mingozzi and P. Toth and C. Sandi},
   pages = {211--235},
   publisher = {Wiley},
   title = {The graph-colouring problem},
   year = {1970},
   annote = {Implicit enumeration algorithm [not seen].}
}

@article{KuJa85,
   author = {M. Kubale and B. Jackowski},
   journal = {Communications of the ACM},
   pages = {412--418},
   title = {A generalized implicit enumeration algorithm for graph coloring},
   volume = {28},
   year = {1985},
   annote = {Presents algorithm and gives experimental comparison to approaches of \cite{Br72,Ch75,Br79,Ko79}.}
}

@inproceedings{KuKu83,
   author = {M. Kubale and E. Kusz},
   address = {Linz},
   booktitle = {Proceedings of the WG'83 International Workshop on Graphtheoretic Concepts in Computer Science},
   editor = {M. Nagl and J. Perl},
   pages = {167--176},
   publisher = {Trauner Verlag},
   title = {Computational experience with implicit enumeration algorithms for graph coloring},
   year = {1983},
   annote = {Experiments with implicit enumeration algorithm [not seen].}
}

@article{La76,
   author = {E. L. Lawler},
   journal = {Information Processing Letters},
   pages = {66--67},
   title = {A note on the complexity of the chromatic number problem},
   volume = {5},
   year = {1976},
   annote = {Reduces worst case running time to $O(2^n )$ from $O(n!)$ at
cost of using exponential space.}
}

@article{Le79,
   author = {F.T. Leighton},
   journal = {Journal of Reasearch of the National Bureau of Standards},
   pages = {489--506},
   title = {A Graph Coloring Algorithm for Large Scheduling Problems},
   volume = {84},
   year = {1979}
}

@article{LoTs82,
   author = {E. Loukakis and C. Tsouros},
   journal = {International Journal of Computer Mathematics},
   pages = {207--220},
   title = {Determining the number of internal stability of a graph},
   volume = {11},
   year = {1982},
   annote = {An implicit enumeration algorithm for finding maximum cliques.
}
}

@inproceedings{LuYa93,
   author = {C. Lund and M. Yannakakis},
   address = {New York, NY},
   booktitle = {Proceedings 25th {ACM} {S}ymposium on {T}heory of {C}omputing},
   pages = {(submitted)},
   publisher = {ACM},
   title = {On the hardness of approximating minimization problems},
   year = {1993},
   annote = {Shows that there is an $\epsilon$ such that no polynomial-time graph coloring heuristic can be guaranteed to get within a factor of $|V|^\epsilon$ of the optimal number of colors unless P = NP.}
}

@article{Ma72,
   author = {D. G. Matula},
   journal = {Networks},
   pages = {29--44},
   title = {Bounded color functions on graphs},
   volume = {2},
   year = {1972},
   annote = {Proposes graph coloring heuristic, analyzed in \cite{Jo74b}.}
}

@inproceedings{MMI72,
   author = {D. W. Matula and G. Marble and J. D. Isaacson},
   address = {New York, NY},
   booktitle = {Graph coloring algorithms},
   editor = {R. C. Read},
   pages = {109--122},
   publisher = {Academic Press},
   title = {Graph Theory and Computing},
   year = {1972},
   annote = {Defines and experimentally analyzes various graph coloring heuristics, including ones involving interchanges of colors.}
}

@inproceedings{MoSh90,
   author = {Craig Morgenstern and Harry Shapiro},
   booktitle = {First {A}nnual {ACM--SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
   title = {Coloration Neighborhood Structures for General Graph Coloring},
   year = {1990},
   annote = {Gives a robust neighborhood structure for local search for graph coloring, with applicability to tabu search and simulated annealing.}
}

@article{MoSh91,
   author = {C. Morgenstern and H. Shapiro},
   journal = {Algorithmica},
   pages = {869--891},
   title = {Heuristics for Rapidly Four--Coloring Large Planar Graphs},
   volume = {6},
   year = {1991}
}

@article{NeTr75,
   author = {George L. Nemhauser and Les E. Trotter},
   journal = {Mathematical Programming},
   pages = {232--248},
   title = {Vertex Packings:  Structural Properties and Algorithms},
   volume = {8},
   year = {1975},
   annote = {A polyhedral approach to vertex packing.  Results include any variable in the linear relaxation to the problem with value 1 occurs in a maximum vertex packing and other results.}
}

@article{Og86,
   author = {Hideo Ogawa},
   journal = {Pattern Recognition},
   number = {1},
   pages = {35--40},
   title = {Labeled Point Pattern Matching by Delaunay Triangulation and Maximal Cliques},
   volume = {19},
   year = {1986},
   annote = {Application of maximum clique to pattern matching.  Pictures made up of points are compared using a related graph.  A clique represents a feasible affine transformation among the associated points.}
}

@inproceedings{OpRo81,
   author = {R.J. Opsut and Fred S. Roberts},
   address = {New York, NY},
   booktitle = {The Theory and Applications of Graphs},
   editor = {G. Chartrand and Y. Alavi and D.L. Goldsmith and L. Lesniak--Foster and D.R. Lick},
   pages = {479--492},
   publisher = {John Wiley \& Sons},
   title = {On the Fleet Maintenance, Movile Radio Frequency, Task Assignment and Traffic Phasing Problems},
   year = {1981},
   annote = {A wealth of applications of graph coloring and (somewhat) cliques.
}
}

@article{PaRo92,
   author = {P. M. Pardalos and G. P. Rodgers},
   journal = {Computers and Operations Research},
   pages = {363--375},
   title = {A branch and bound algorithm for the maximum clique problem},
   volume = {19},
   year = {1992},
   annote = {Uses quadratic programming for its bounding technique.  Algorithm is designed to work well on dense graphs.}
}

@article{PaXu93,
   author = {P. M. Pardalos and J. Xue},
   journal = {Journal of Global Optimization},
   pages = {(to appear)},
   title = {The maximum clique problem},
   year = {1993},
   annote = {Extensive survey with almost 300 references.  Should be
available via anonymous FTP from DIMACS (in {\tt pub/challenge/graph/contributed/pardalos}.}
}

@article{Pe83,
   author = {J. Peem\"{o}ller},
   journal = {Communications of the ACM},
   pages = {595--597},
   title = {A correction to {B}r\'elaz's modification of {B}rown's coloring algorithm},
   volume = {26},
   year = {1983},
   annote = {Corrects implicit enumeration algorithm in \cite{Br79}.}
}

@article{Pi82,
   author = {B. Pittel},
   journal = {Mathematical Proceedings of the Cambride Philosophical Society},
   pages = {511--526},
   title = {On the Probable Behaviour of Some Algorithms for Finding the Stability Number of a Graph},
   volume = {92},
   year = {1982},
   annote = {A number of heuristics are examined for random graphs.  None get within a factor of 2.}
}

@article{TaTr77,
   author = {Robert E. Tarjan and A.E. Trojanowski},
   journal = {SIAM Journal on Computing},
   pages = {266--283},
   title = {Finding a Maximum Independent Set},
   volume = {6},
   year = {1977},
   annote = {An implicit enumearation algorithm for maximum clique.  Worst case running time is $O(2^{n/3})$.}
}

@article{Tu88,
   author = {J. S. Turner},
   journal = {Journal of Algorithms},
   pages = {63--82},
   title = {Almost all $k$-colorable graphs are easy to color},
   volume = {9},
   year = {1988},
   annote = {Designs fast algorithms that optimally color random graphs
with a given chromatic number quickly.}
}

@book{VaAa87,
   author = {Van Laarhoven, P.J.M and E.H.L. Aarts},
   address = {Dordrrecht, The Netherlands},
   publisher = {Kluwer Academic Publishers},
   title = {Simulated Annealing:  Theory and Practice},
   year = {1987},
   annote = {A very extensive bibliography and an overview of issues in simulated annealing.}
}

@article{WePo67,
   author = {D.J.A. Welsh and M.B. Powell},
   journal = {Computer Journal},
   pages = {85--86},
   title = {An Upper Bound on the Chromatic Number of a Graph and its Application to Timetabling Problems},
   volume = {10},
   year = {1967},
   annote = {An early heuristic for graph coloring}
}

@article{Wi83,
   author = {A. Wigderson},
   journal = {Journal of the Association for Computing Machinery},
   pages = {729--735},
   title = {Improving the Performance Guarantee of Approximate Graph Coloring},
   volume = {30},
   year = {1983},
   annote = {A modified successive approximation heuristic to reduce the worst case behavior of the heuristic.}
}

@inproceedings{Wi70,
   author = {M. R. Williams},
   address = {New York},
   booktitle = {Combinatorial Structures and their Applications},
   pages = {477--478},
   publisher = {Gordon and Breach},
   title = {The coloring of very large graphs},
   year = {1970},
   annote = {Proposes graph coloring heuristic, analyzed in \cite{Jo74b}.}
}

@article{Wo69,
   author = {D. C. Wood},
   journal = {The Computer Journal},
   pages = {317--319},
   title = {A technique for coloring a graph applicable to large scale time-tabling problems},
   volume = {3},
   year = {1969},
   annote = {Proposes graph coloring heuristic, analyzed in \cite{Jo74b}.}
}

@misc{YGC92,
   author = {G. Yu and O. Goldschmidt and H. Chen},
   howpublished = {ORSA/TIMS Presentation, San Francisco, CA},
   title = {Clique, Independent Set, and Vertex Cover in Geometric Graphs},
   year = {1992}
}

@misc{YKL92,
   author = {G. Yu and P. Kouvelis and Luo},
   howpublished = {ORSA/TIMS Presentation, San Francisco, CA},
   title = {A Weighted Vertex Packing Problem for Specially Structured Geometric Graphs Arising in the Design of Electronic Testing Fixtures},
   year = {1992}
}