\begin{thebibliography}{100}

\bibitem{cl:ani86}
A.~V. Anisimov.
\newblock Local optimization of graph coloring.
\newblock {\em Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk
  Ukrainskoi SSR. Kibernetika}, (6):1--8,133, 1986.
\newblock number or volume?

\bibitem{cl:apha77}
K.~Appel and W.~Haken.
\newblock Every planar map is four colorable: Part 1, discharging.
\newblock {\em Illinois Journal of Mathematics}, 21:429--490, 1977.

\bibitem{cl:ahk}
K.~Appel, W.~Haken, and J.~Koch.
\newblock Every planar map is four colorable: Part 2, reducibility.
\newblock {\em Illinois Journal of Mathematics}, 21:491--567, 1977.

\bibitem{cl:abn61}
J.~S. Appleby, D.~V. Blake, and E.~A. Newman.
\newblock Techniques for producing school timetables on a computer and their
  application to other scheduling problems.
\newblock {\em The Computer Journal}, 3:237--245, 1961.

\bibitem{cl:arj80}
E.~Arjomandi.
\newblock An efficient algorithm for colouring the edges of a graph with delta
  + 1 colours.
\newblock Technical Report~1, York University, Department of Computer Science,
  1980.
\newblock Subfile: STR (Stanford Technical Reports).

\bibitem{cl:asgi84}
Bengt Aspvall and John~R. Gilbert.
\newblock Graph coloring using eigenvalue decomposition.
\newblock {\em SIAM Journal on Algebraic and Discrete Methods}, 5(4):526--538,
  1984.

\bibitem{cl:adp80}
G.~Ausiello, A.~D'Atri, and M.~Protasi.
\newblock Structure preserving reductions among convex optimization problems.
\newblock {\em Journal of Computer and System Sciences}, 21:136--153, 1980.

\bibitem{cl:bayu86}
Egon Balas and Chang~Sung Yu.
\newblock Finding a maximum clique in an arbitrary graph.
\newblock {\em SIAM Journal on Computing}, 15(4):1054--1068, 1986.

\bibitem{cl:bapo90}
Pierre Baldi and Edward~C. Posner.
\newblock Graph coloring bounds for cellular radio.
\newblock {\em Computers and Mathematics with Applications}, 19(10):91--97,
  1990.

\bibitem{cl:baev83}
R.~Bar-Yehuda and S.~Even.
\newblock A $2-{{\log\log n} \over {2 \log n}}$ performance ratio for the
  weighted vertex cover problem.
\newblock Technical Report \#260, Technion Haifa, January 1983.
\newblock NCPY.

\bibitem{cl:bewi85}
Edward~A. Bender and Herbert~S. Wilf.
\newblock A theoretical analysis of backtracking in the graph coloring problem.
\newblock {\em Journal of Algorithms}, 6(2):275--282, 1985.

\bibitem{cl:bedu84}
C.~Berge and P.~Duchet.
\newblock Strongly perfect graphs.
\newblock {\em Annals of Discrete Mathematics}, 21:57--61, 1984.

\bibitem{cl:ber78}
Claude Berge.
\newblock {\em Algorithms and extremal problems for equipartite colorings in
  graphs and hypergraphs}, volume~2 of {\em Annals of Discrete Mathematics},
  pages 149--150.
\newblock North-Holland Publishing Co., 1978.

\bibitem{cl:bero90}
Bonnie Berger and John Rompel.
\newblock A better performance guarantee for approximate graph coloring.
\newblock {\em Algorithmica}, 5(4):459--466, 1990.

\bibitem{cl:bire75}
J.~R. Bitner and E.~Reingold.
\newblock Backtrack programming techniques.
\newblock {\em Communications of the ACM}, 18:651--656, 1975.

\bibitem{cl:blum90}
Avrim Blum.
\newblock Some tools for approximate 3-coloring.
\newblock In {\em 31st Annual Symposium on Foundations of Computer Science},
  pages 554--562, 1990.

\bibitem{cl:blu89}
Avrin Blum.
\newblock An $\tilde{O}(n^{0.4})$-approximation algorithm for 3-coloring (and
  improved approximation algorithms for $k$-coloring).
\newblock In {\em Proceedings of the Twenty First Annual ACM Symposium on
  Theory of Computing}, pages 535--542, 1989.

\bibitem{cl:bol88}
B.~Bollob\'{a}s.
\newblock The chromatic number of random graphs.
\newblock {\em Combinatorica}, 8(1):49--55, 1988.

\bibitem{cl:boer76}
B.~Bollob\'{a}s and P.~Erd\"{o}s.
\newblock Cliques in random graphs.
\newblock {\em Mathematical Proceedings of the Cambridge Philosophical
  Society}, 80(41):419--427, 1976.

\bibitem{cl:boll78}
B\'{e}la Bollob\'{a}s.
\newblock Chromatic number, girth and maximal degree.
\newblock {\em Discrete Mathematics}, 24:311--314, 1978.

\bibitem{cl:both85}
B\'{e}la Bollob\'{a}s and Andrew Thomason.
\newblock Random graphs of small order.
\newblock In {\em Random Graphs '83}, volume~28 of {\em Annals of Discrete
  Mathematics}, pages 47--97. North-Holland Publishing Co., 1985.
\newblock Section 6: ``Colouring large random graphs''.

\bibitem{cl:bon69}
J.~A. Bondy.
\newblock Bounds for the chromatic number of a graph.
\newblock {\em Journal of Combinatorial Theory}, 7:96--98, 1969.

\bibitem{cl:boha90}
Ravi Boppana and Magnus Halldorsson.
\newblock Approximating maximum independent sets by excluding subgraphs.
\newblock In {\em SWAT 90 2nd Scandinavian Workshop on Algorithm Theory},
  volume~3 of {\em Lecture Notes in Computer Science}, pages 13--25, 1990.

\bibitem{cl:boka87}
Joan~F. Boyar and Howard~J. Karloff.
\newblock Coloring planar graphs in parallel.
\newblock {\em Journal of Algorithms}, 8:470--479, 1987.

\bibitem{cl:bre79}
Daniel Br\'{e}laz.
\newblock New methods to color the vertices of a graph.
\newblock {\em Communications of the ACM}, 22(4):251--256, April 1979.

\bibitem{cl:bro64}
Sol Broder.
\newblock Final examination scheduling.
\newblock {\em Communications of the ACM}, 7(8):494--498, August 1964.

\bibitem{cl:brke73}
Coen Bron and Joep Kerbosch.
\newblock Algorithm 457: Finding all cliques of an undirected graph.
\newblock {\em Communications of the ACM}, 16(9):575--577, 1973.

\bibitem{cl:bro41}
R.~L. Brooks.
\newblock On coloring the nodes of a network.
\newblock {\em Mathematical Proceedings of the Cambridge Philosophical
  Society}, 37:194--197, 1941.

\bibitem{cl:bro72}
J.~Randall Brown.
\newblock Chromatic scheduling and the chromatic number problem.
\newblock {\em Management Science}, 19(4):456--463, 1972.
\newblock Part I.

\bibitem{cl:bksw90}
Jason~I. Brown, David kelly, J.~Schonheim, and Robert~E. Woodrow.
\newblock Graph coloring satisfying restraints.
\newblock {\em Discrete Mathematics}, 80(2):123--143, 1990.

\bibitem{cl:bms80}
E.~Burattini, A.~Massarotti, and A.~Santaniello.
\newblock A graph colouration technique.
\newblock In {\em Second International Conference on Information Sciences and
  Systems (Univ. Patras, Patras, 1979), Vol. III}, pages 326--333. Reidel,
  1980.

\bibitem{cl:cath85}
Jane Cameron and Gomer Thomas.
\newblock An approximate graph partitioning algorithm and its computational
  complexity.
\newblock {\em Congressus Numerantium}, 49:287--293, 1985.

\bibitem{cl:chl87}
G.~Campers, O.~Henkes, and J.~P. Leclercq.
\newblock Sur les methodes exactes de coloration de graphes. {O}n exact methods
  of graph coloring.
\newblock {\em Cahiers du Centre d'Etudes de Recherche Operationnelle},
  29(1--2):19--30, 1987.

\bibitem{cl:chl88}
G.~Campers, O.~Henkes, and J.~P. Leclerq.
\newblock Graph coloring heuristics: a survey, some new propositions and
  computational experiences on random and ``{L}eighton's'' graphs.
\newblock In {\em Operational research '87 (Buenos Aires, 1987)}, pages
  917--932. North-Holland Publishing Co., 1988.

\bibitem{cl:capa90}
R.~Carraghan and P.~M. Pardalos.
\newblock An exact algorithm for the maximum clique problem.
\newblock {\em Operations Research Letters}, 9:375--382, 1990.

\bibitem{cl:cat85}
Paul~A. Catlin.
\newblock Homomorphisms as a generalization of graph coloring.
\newblock {\em Congressus Numerantium}, 50:179--186, 1985.

\bibitem{cl:chw87}
M.~Chams, A.~Hertz, and D.~de~Werra.
\newblock Some experiments with simulated annealing for coloring graphs.
\newblock {\em European Journal of Operational Research}, 32(2):260--266, 1987.

\bibitem{cl:che86}
Ya.~I. Cheban.
\newblock Investigation of a generalized graph coloring problem.
\newblock In {\em Investigation of methods for solving extremal problems
  (Russian)}, vii, pages 77--81. Akad. Nauk Ukrain. SSR, Inst. Kibernet., Kiev,
  1986.

\bibitem{cl:ckt91}
Peter Cheeseman, Bob Kanefsky, and William~M. Taylor.
\newblock Where the {\em really} hard problems are.
\newblock In {\em International Joint Conference on Artificial Intelligence},
  pages 331--337, 1991.

\bibitem{cl:chsl84}
M.~Chorbak and M.~\'{S}lusarek.
\newblock Problem 84-23.
\newblock {\em Journal of Algorithms}, 5:588, 1984.

\bibitem{cl:chr71}
N.~Christofides.
\newblock An algorithm for the chromatic number of a graph.
\newblock {\em Computing}, 14:38--39, 1971.

\bibitem{cl:chv84}
V.~Chv\'{a}tal.
\newblock Perfectly ordered graphs.
\newblock In C.~Berge and V.~Chv\'{a}tal, editors, {\em Topics on Perfect
  Graphs}, volume~21 of {\em Annals of Discrete Mathematics}. North-Holland
  Publishing Co., 1984.

\bibitem{cl:cgj78}
V.~Chv\'{a}tal, M.~R. Garey, and D.~S. Johnson.
\newblock Two results concerning multicoloring.
\newblock volume~2 of {\em Annals of Discrete Mathematics}, pages 151--154.
  North-Holland Publishing Co., 1978.
\newblock booktitle?

\bibitem{cl:chhmw87}
V.~Chv\'{a}tal, C.~T. Hoang, N.~V.~R. Mahadev, and D.~de~Werra.
\newblock Four classes of perfectly orderable graphs.
\newblock {\em Journal of Graph Theory}, 11:481--495, 1987.

\bibitem{cl:col64}
A.~J. Cole.
\newblock The preparation of examination time-tables using a small-store
  computer.
\newblock {\em The Computer Journal}, 7:117--121, 1964.

\bibitem{cl:como83}
T.~F. Coleman and J.~J. More.
\newblock Estimation of sparse jacobian matrices and graph coloring problems.
\newblock {\em SIAM Journal on Numerical Analysis}, 20(1):187--209, 1983.

\bibitem{cl:como84}
Thomas~F. Coleman and Jorge~J. More.
\newblock Estimation of sparse hessian matrices and graph coloring problems.
\newblock {\em Mathematical Programming}, 28(3):243--270, 1984.

\bibitem{cl:coo75}
R.~J. Cook.
\newblock Chromatic number and girth.
\newblock {\em Periodica Mathematica Hungarica}, 6(1):103--107, 1975.

\bibitem{cl:cogr73}
D.~G. Corneil and B.~Graham.
\newblock An algorithm for determining the chromatic number of a graph.
\newblock {\em SIAM Journal on Computing}, 2(4):311--318, 1973.

\bibitem{cl:cul92a}
Joseph~C. Culberson.
\newblock Iterated greedy graph coloring and the difficulty landscape.
\newblock Technical Report TR 92-07, University of Alberta Department of
  Computing Science, Edmonton, Alberta Canada T6G 2H1, 1992.
\newblock ftp ftp.cs.ualberta.ca pub/TechReports.

\bibitem{cl:dai80}
D.~P. Dailey.
\newblock Uniqueness of colorability and colorability of planar 4-regular
  graphs are {NP}-complete.
\newblock {\em Discrete Mathematics}, 30:289--293, 1980.

\bibitem{cl:veg85}
W.~Fernandex de~la Vega.
\newblock Random graphs almost optimally colorable in polynomial time.
\newblock In {\em Random Graphs '83}, volume~28 of {\em Annals of Discrete
  Mathematics}, pages 311--317. North-Holland Publishing Co., 1985.

\bibitem{cl:veg84}
W.~Fernandez de~la Vega.
\newblock On the chromatic number of sparse random graphs.
\newblock In B.~Bollob\'{a}s, editor, {\em Graph theory and combinatorics,
  Proceedings {C}ambridge combinatorial conference in hobour of {P}aul
  {E}rd\"{o}s}, pages 321--328. Academic Press, Inc., 1984.

\bibitem{cl:wer74b}
D.~de~Werra.
\newblock How to color a graph.
\newblock In B.~Roy, editor, {\em Combinatorial Programming --- Methods and
  Applications}, pages 305--325. NATO Advanced Science Institute Series C:
  Mathematical and Physical Sciences, 1974.
\newblock Vol. 19.

\bibitem{cl:wer74a}
D.~de~Werra.
\newblock Some results in chromatic scheduling.
\newblock {\em Z. operations Res. Ser. A}, 16:167--175, 1974.

\bibitem{cl:wer75}
D.~de~Werra.
\newblock On a particular conference scheduling problem.
\newblock {\em INFOR---Canadian Journal of Operational Research and Information
  Processing}, 13:308--315, 1975.

\bibitem{cl:ddh84}
Peter Dencker, Karl Durre, and Johannes Heuft.
\newblock Optimization of parser tables for portable compilers.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  6(4):546--572, 1984.

\bibitem{cl:des47}
Blanches Descartes.
\newblock A three colour problem.
\newblock {\em Eureka}, April 1947.
\newblock solution march 1948; pseudonym for Tutte.

\bibitem{cl:des54}
Blanches Descartes.
\newblock Solution to advanced problem 4526.
\newblock {\em The American Mathematical Monthly}, 61:352, 1954.
\newblock proposed by P. Ungar; psuedonym for Tutte.

\bibitem{cl:dik86}
Krzysztof Diks.
\newblock A fast parallel algorithm for six-colouring of planar graphs
  (extended abstract).
\newblock In J.~Gruska, B.~Rovan, and J.~Wiedermann, editors, {\em Mathematical
  foundations of computer science 1986; Proceedings of the twelfth symposium
  held in Bratislava}, volume 233 of {\em Lecture Notes in Computer Science},
  pages 273--282. Springer-Verlag, 1986.

\bibitem{cl:dir53}
G.~A. Dirac.
\newblock The structure of k-chromatic graphs.
\newblock {\em Fundamenta Mathematicae}, 40:42--55, 1953.
\newblock color.

\bibitem{cl:dun76}
F.~D.~J. Dunstan.
\newblock Sequential colourings of graphs.
\newblock In {\em Proceedings of Fifth British Combinatorial Conference}, pages
  151--158. Utilitas Mathematica, 1976.

\bibitem{cl:dur73}
K.~D\"{u}rre.
\newblock An algorithm for coloring the vertices of an arbitrary graph.
\newblock In P.~Deussen, editor, {\em unknown}, volume~78 of {\em Lecture Notes
  in Economics and Mathematical Systems}, pages 82--89. Springer-Verlag, 1973.

\bibitem{cl:dhm82}
K.~D\"{u}rre, J.~Heuft, and H.~Muller.
\newblock Worst and best case behaviour of an approximate graph coloring
  algorithm.
\newblock In J.~R. Muhlbacher and Carl~Hansen Verlag, editors, {\em Proc. 7th
  conference on graphtheoretic concepts in computer science (Linz, Austria,
  June 15-17, 1981)}, pages 339--348, Munich, 1982.

\bibitem{cl:dubr81}
R.~D. Dutton and R.~C. Brigham.
\newblock A new graph coloring algorithm.
\newblock {\em The Computer Journal}, 24(1):85--86, 1981.

\bibitem{cl:dyfr86}
M.~E. Dyer and A.~M. Frieze.
\newblock Fast solution of some random {NP}-hard problems.
\newblock In {\em 27th Annual Symposium on Foundations of Computer Science},
  pages 331--336, 1986.

\bibitem{cl:dyfr89}
M.~E. Dyer and A.~M. Frieze.
\newblock The solution of some random {NP}-hard problems in polynomial expected
  time.
\newblock {\em Journal of Algorithms}, 10:451--489, 1989.

\bibitem{cl:ear68}
S.~Early.
\newblock {\em Evaluating a Timetabling Algorithm Based on Graph Recolouring}.
\newblock PhD thesis, University of Oxford, 1968.
\newblock B. Phil. Diss.

\bibitem{cl:elle89}
J.~A. Ellis and P.~M. Lepolesa.
\newblock A {L}as {V}egas coloring algorithm.
\newblock {\em The Computer Journal}, 32(5):474--476, 1989.

\bibitem{cl:erd59}
P.~Erd\"{o}s.
\newblock Graph theory and probability.
\newblock {\em Canadian Journal of Mathematics}, 11:34--38, 1959.

\bibitem{cl:erwi77}
P.~Erd\"{o}s and R.~J. Wilson.
\newblock On the chromatic index of almost all graphs.
\newblock {\em Journal of Combinatorial Theory Series B}, 23:255--257, 1977.

\bibitem{cl:erer86}
Marcel Erne and Paul Erd\"{o}s.
\newblock Clique numbers of graphs.
\newblock {\em Discrete Mathematics}, 59(3):235--241, 1986.

\bibitem{cl:femo91}
Feder and Motwani.
\newblock Clique partitions, graph compression and speeding up algorithms.
\newblock In {\em Proceedings of the Twenty Third Annual Symposium on Theory of
  Computing}, pages 123--3, 1991.

\bibitem{cl:fglss91}
U.~Feige, S.~Goldwasser, L.~Lovasz, S.~Safra, and M.~Szegedy.
\newblock Approximating clique is almost {NP}-complete.
\newblock In {\em 32nd Annual Symposium on Foundations of Computer Science},
  pages 2--3, 1991.

\bibitem{cl:fiwi77}
Stanley Fiorini and Robin~J. Wilson.
\newblock Edge-colorings of graphs.
\newblock volume~16 of {\em Lecture Notes in Mathematics}, pages 102--126.
  Pitman, 1977.
\newblock booktitle?

\bibitem{cl:for69}
J.~A. Formby.
\newblock A computer procedure for bounding the chromatic number of a graph.
\newblock In D.~J.~A. Welsh, editor, {\em Combinatorial Mathematics and its
  Applications}, pages 111--114, Proceedings of a Conference in Oxford, July
  1969. Academic Press, Inc.

\bibitem{cl:fre82}
E.~C. Freuder.
\newblock A sufficient condition of backtrack-free search.
\newblock {\em Journal of the ACM}, 29(1):24--32, 1982.

\bibitem{cl:fhw89}
C.~Friden, A.~Hertz, and D.~de~Werra.
\newblock {STABULUS:} {A} technique for finding stable sets in large graphs
  with tabu search.
\newblock {\em Computing}, 42:35--44, 1989.

\bibitem{cl:fri90b}
Alan~M. Frieze.
\newblock On the independence number of random graphs.
\newblock {\em Discrete Mathematics}, 81:171--175, 1990.

\bibitem{cl:fri90a}
Alan~M. Frieze.
\newblock Parallel colouring of random graphs.
\newblock In M.~Karo\'{n}ski, J.~Jaworski, and A.~Rudi\'{n}ski, editors, {\em
  Random Graphs '87}, pages 41--52. John Wiley \& Sons, Inc., 1990.

\bibitem{cl:fusu92}
Martin F\"{u}rer and C.~R. Subramanian.
\newblock Coloring random graphs.
\newblock In {\em The Third Scandinavian Workshop on Algorithm Theory (SWAT
  '92)}, 1992.
\newblock preprint.

\bibitem{cl:gaka}
Harold~N. Gabow and Oded Kariv.
\newblock Algorithms for edge coloring bipartite graphs and multigraphs.
\newblock {\em SIAM Journal on Computing}, 11(1):117--129, 1982.

\bibitem{cl:gajo75e}
M.~R. Garey and D.~S. Johnson.
\newblock On {S}alazar and {O}akford.
\newblock {\em Communications of the ACM}, 18:240--241, 1975.

\bibitem{cl:gajo76}
M.~R. Garey and D.~S. Johnson.
\newblock The complexity of near-optimal graph coloring.
\newblock {\em Journal of the ACM}, 23:43--49, 1976.

\bibitem{cl:gjs76}
M.~R. Garey, D.~S. Johnson, and I.~Stockmeyer.
\newblock Some simplified {NP}-complete graph problems.
\newblock {\em Theoretical Computer Science}, 1:237--267, 1976.

\bibitem{cl:gav72}
F\v{a}nic\v{a} Gavril.
\newblock Algorithms for coloring, maximum clique, minimum covering by cliques,
  and maximum independent set of a chordal graph.
\newblock {\em SIAM Journal on Applied Mathematics}, 1(2):181--187, 1972.

\bibitem{cl:geli79}
L.~Gerhards and W.~Lindenberg.
\newblock Clique detection for nondirected graphs.
\newblock {\em Computing}, 21:295--322, 1979.

\bibitem{cl:gio87}
Mario Gionfriddo.
\newblock A short survey of some generalized colourings of graphs.
\newblock {\em Ars Combinatoria}, 24(B):155--163, 1987.

\bibitem{cl:glo86}
F.~Glover.
\newblock Future paths for integer programming and links to artificial
  intelligence.
\newblock {\em Computers and Operations Research}, 13:533--549, 1986.

\bibitem{cl:goba65}
S.~W. Golomb and L.~D. Baumert.
\newblock Backtrack programming.
\newblock {\em Journal of the ACM}, 12:516--524, 1965.

\bibitem{cl:gri83}
Jerrold~R. Griggs.
\newblock Lower bounds on the independence number in terms of the degrees.
\newblock {\em Journal of Combinatorial Theory Series B}, 34:22--39, 1983.

\bibitem{cl:grmc75}
G.~R. Grimmett and C.~J.~H. McDiarmid.
\newblock On colouring random graphs.
\newblock {\em Mathematical Proceedings of the Cambridge Philosophical
  Society}, 77:313--324, 1975.

\bibitem{cl:gru70}
B.~Gr\"{u}nbaum.
\newblock A problem in graph colouring.
\newblock {\em The American Mathematical Monthly}, 77:1088--1092, 1970.

\bibitem{cl:gya85}
A.~Gy\'{a}rf\'{a}s.
\newblock Problems from the world surrounding perfect graphs.
\newblock Research Report 177, Computer and Automation Institute Studies, 1985.

\bibitem{cl:gyle88}
A.~Gyarfas and J.~Lehel.
\newblock On-line and first fit colorings of graphs.
\newblock {\em Journal of Graph Theory}, 12(2):217--227, 1988.

\bibitem{cl:gyle91}
Andr\'{a}s Gy\'{a}rf\'{a}s and Jen\"{o} Lehel.
\newblock Online coloring of $p_5$-free graphs.
\newblock {\em Combinatorica}, 11(2):181--184, 1991.

\bibitem{cl:hpv92}
Jonas Hasselberg, Panos~M. Pardalos, and George Vairaktarakis.
\newblock Test case generators and computational results for the maximum clique
  problem.
\newblock ftp dimacs.rutgers.edu pub/challenge/graph/contributed, 1992.
\newblock Working Paper.

\bibitem{cl:hed85}
Bruce Hedman.
\newblock The maximum number of cliques in dense graphs.
\newblock {\em Discrete Mathematics}, 54(2):161--166, 1985.

\bibitem{cl:heki81}
P.~Hell and D.~G. Kirkpatrick.
\newblock Scheduling, matching, and coloring.
\newblock In {\em Algebraic methods in graph theory, Vol. I, II}, Colloq. Math.
  Soc. Janos Bolyai, 25, pages 273--279. North-Holland Publishing Co., 1981.

\bibitem{cl:hewe87}
A.~Hertz and D.~de~Werra.
\newblock Using tabu search techniques for graph coloring.
\newblock {\em Computing}, 39(4):345--351, 1987.

\bibitem{cl:hrs73}
A.~J.~W. Hilton, R.~Rado, and S.~H. Scott.
\newblock A $(<5)$-color theorem for planar graphs.
\newblock {\em Bull. London Math. Soc.}, 5:302--306, 1973.
\newblock NCPY.

\bibitem{cl:hiwi89}
A.~J.~W. Hilton and Robin~J. Wilson.
\newblock Edge colorings of graphs: A progress report.
\newblock In {\em Graph Theory and its Applications East and West: Proceedings
  of the First China-USA International Graph Theory Conference}, volume 576 of
  {\em Annals of the New York Academy of Sciences}, pages 241--249, 1989.

\bibitem{cl:hoe88}
Cornelis Hoede.
\newblock Hard graphs for the maximum clique problem.
\newblock {\em Discrete Mathematics}, 72(1--3):175--179, 1988.

\bibitem{cl:hol69}
P.~Holgate.
\newblock Majorants of the chromatic number of a random graph.
\newblock {\em J. Roy. Statist. Soc. Ser. B.}, 31:303--309, 1969.

\bibitem{cl:host85}
Glenn Hopkins and William Staton.
\newblock Graphs with unique maximum independent sets.
\newblock {\em Discrete Mathematics}, 57(3):245--251, 1985.

\bibitem{cl:ira90}
Sandy Irani.
\newblock Coloring inductive graphs on-line.
\newblock In {\em 31st Annual Symposium on Foundations of Computer Science},
  pages 470--479, 1990.

\bibitem{cl:jag92}
Arun Jagota.
\newblock Efficiently approximating max-clique in a hopfield-style network.
\newblock In {\em Proceedings of International Joint Conference on Neural
  Networks '92 Volume II}, pages 248--253, 1992.
\newblock ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

\bibitem{cl:jare92}
Arun Jagota and Kenneth~W. Regan.
\newblock Performance of max-clique approximation heuristics under
  description-length weighted distributions.
\newblock Technical report, Department of Computer Science, State University at
  New York at Buffalo, 1992.
\newblock ftp ftp.cs.buffalo.edu users/jagota or ftp dimacs.rutgers.edu
  pub/challenge/graph/contributed.

\bibitem{cl:josa89}
Garry Johns and Farrokh Saba.
\newblock On the path-chromatic number of a graph.
\newblock In {\em Graph Theory and its Applications East and West: Proceedings
  of the First China-USA International Graph Theory Conference}, volume 576 of
  {\em Annals of the New York Academy of Sciences}, pages 275--280, 1989.

\bibitem{cl:joh74b}
D.~S. Johnson.
\newblock Approximation algorithms for combinatorial problems.
\newblock {\em Journal of Computer and System Sciences}, 9:256--278, 1974.

\bibitem{cl:joh74a}
D.~S. Johnson.
\newblock Worst-case behavior of graph-coloring algorithms.
\newblock In {\em Proceedings of 5th Southeastern Conference on Combinatorics,
  Graph Theory and Computing}, pages 513--528, Winnipeg, 1974. Utilitas
  Mathematica.

\bibitem{cl:jyp88}
D.~S. Johnson, M.~Yannakakis, and C.~H. Papadimitriou.
\newblock On generating all maximal independent sets.
\newblock {\em Information Processing Letters}, 27:119--123, 1988.

\bibitem{cl:jams91}
David~S. Johnson, Cecilia~R. Aragon, Lyle~A. McGeoch, and Catherine Schevon.
\newblock Optimization by simulated annealing: An experimental evaluation; part
  {II}, graph coloring and number partitioning.
\newblock {\em Operations Research}, 39(3):378--406, may-june 1991.

\bibitem{cl:joma82}
A.~Johri and D.~W. Matula.
\newblock Probabilistic bounds and heuristic algorithms.
\newblock Technical Report 82-CSE-06, Southern Methodist University, Department
  of Computer Science, 1982.
\newblock Supposed to have appeared?

\bibitem{cl:kan92}
Viggo Kann.
\newblock On the approximability of the maximum common subgraph problem.
\newblock In {\em STACS 92}, pages 377--388, 1992.

\bibitem{cl:kar72}
R.~M. Karp.
\newblock Reducibility among combinatorial problems.
\newblock In R.~E. Miller and J.~W. Thatcher, editors, {\em Complexity of
  Computer Computations}, pages 85--104. Plennum Press, New York, 1972.
\newblock NCPY.

\bibitem{cl:knn82}
Tsuyoshi Kawaguchi, Hideo Nakano, and Yoshiro Nakanishi.
\newblock Probabilistic analysis of a heuristic graph coloring algorithm.
\newblock {\em Electron. Comm. Japan}, 65(6):12--18, 1982.

\bibitem{cl:keke54}
J.~B. Kelly and L.~M. Kelly.
\newblock Paths and circuits in critical graphs.
\newblock {\em American Journal of Mathematics}, 76:786--792, 1954.
\newblock theory graph coloring.

\bibitem{cl:khe88}
E.~M. Kheifets.
\newblock Planning of operation of communications links in packet radio
  networks using a graph-coloring algorithm.
\newblock {\em Automatic Control and Computer Sciences}, 22(5):34--37, 1988.

\bibitem{cl:khu90b}
Samir Khuller.
\newblock Coloring algorithms for $k_5$-minor free graphs.
\newblock {\em Information Processing Letters}, 34:203--208, 1990.

\bibitem{cl:khu90a}
Samir Khuller.
\newblock Extending planar graph algorithms to $k_{3,3}$-free graphs.
\newblock {\em Information and Computation}, 84(1):13--25, 1990.

\bibitem{cl:kgv83}
S.~Kirkpatrick, C.~D.~Gelatt\ Jr., and M.~P. Vecchi.
\newblock Optimization by simulated annealing.
\newblock {\em Science}, 220(4598):671--679, May 1983.

\bibitem{cl:koma75}
R.~R. Korfhage and D.~W. Matula.
\newblock On {S} and {O}; more on the {S}alazar and {O}akford paper.
\newblock {\em Communications of the ACM}, 18:240,303, 1975.

\bibitem{cl:kor79}
S.~M. Korman.
\newblock the graph-colouring problem.
\newblock In N.~Christofides, A.~Mingozzi, P.~Toth, and C.~Sandi, editors, {\em
  Combinatorial Optimization}, pages 211--235. John Wiley \& Sons, Inc., 1979.

\bibitem{cl:kor80}
A.~D. Korshunov.
\newblock The chromatic number of $n$-vertex graphs.
\newblock {\em Diskret. Analiz}, 35:15--44, 1980.
\newblock in Russian.

\bibitem{cl:kuku83}
M.~Kubale and E.~Kusz.
\newblock Computer experiences with implicit enumeration algorithms for graph
  coloring.
\newblock In M.~Nagl and J.~Perl, editors, {\em International workshop on
  graphtheoretic concepts in computer science. Proceedings of the WG '83},
  pages 167--176, Linz, Austria, 1983. Universitatsverlag Rudolf Trauner.
\newblock GCL (ACM Guide to Computing Literature) ACM.

\bibitem{cl:kuja85}
Marek Kubale and Boguslaw Jackowski.
\newblock A generalized implicit enumeration algorithm for graph coloring.
\newblock {\em Communications of the ACM}, 28(4):412--418, 1985.

\bibitem{cl:kuc77}
Lud\u{e}k Ku\u{c}era.
\newblock Expected behavior of graph coloring algorithms.
\newblock In {\em FCT '77}, volume~56 of {\em Lecture Notes in Computer
  Science}, pages 447--451. Springer-Verlag, Berlin, 1977.

\bibitem{cl:kuc89}
Lud\u{e}k Ku\u{c}era.
\newblock Graphs with small chromatic numbers are easy to color.
\newblock {\em Information Processing Letters}, 30:233--236, 1989.

\bibitem{cl:kuc91}
Lud\u{e}k Ku\u{c}era.
\newblock A generalized encryption scheme based on random graphs.
\newblock In {\em 17th Annual Workshop on Graph-Theoretic Concepts in Computer
  Science {(WG91)}}, volume 570 of {\em Lecture Notes in Computer Science},
  pages 180--186. Springer-Verlag, Berlin, 1991.

\bibitem{cl:lawxx}
E.~L. Lawler.
\newblock A note on the complexity of the chromatic number problem.
\newblock {\em Information Processing Letters}, 5:66--67, year?
\newblock full reference.

\bibitem{cl:lei79}
F.~T. Leighton.
\newblock A graph colouring algorithm for large scheduling problems.
\newblock {\em J. Res. Nat. Bur. Stand.}, 84:489--496, 1979.

\bibitem{cl:liva89}
N.~Linial and U.~Vazirani.
\newblock Graph products and chromatic numbers.
\newblock In {\em 30th Annual Symposium on Foundations of Computer Science},
  pages 124--128, 1989.

\bibitem{cl:lin86}
Nathan Linial.
\newblock Graph coloring and monotone functions on posets.
\newblock {\em Discrete Mathematics}, 58(1):97--98, 1986.

\bibitem{cl:lita79}
Richard Lipton and Robert Tarjan.
\newblock A separator theorem for planar graphs.
\newblock {\em SIAM Journal on Applied Mathematics}, 36:346--358, 1979.

\bibitem{cl:lita80}
Richard Lipton and Robert Tarjan.
\newblock Applications of a planar separator theorem.
\newblock {\em SIAM Journal on Computing}, 9(3):615--626, 1980.

\bibitem{cl:losa86}
Vahid Lotfi and Sanjiv Sarin.
\newblock A graph coloring algorithm for large scale scheduling problems.
\newblock {\em Computers and Operations Research}, 13(1):27--32, 1986.

\bibitem{cl:lou83}
E.~Loukakis.
\newblock A new backtracking algorithm for generating the family of maximal
  independent sets of a graph.
\newblock {\em Computers and Mathematics with Applications}, 9:583--589, 1983.

\bibitem{cl:lots82}
E.~Loukakis and C.~Tsouros.
\newblock Determining the number of internal stability of a graph.
\newblock {\em International Journal of Computer Mathematics}, 11:207--220,
  1982.

\bibitem{cl:lov66}
L.~lov\'{a}sz.
\newblock On decomposition of graphs.
\newblock {\em Studia Sci. Math. Hungar.}, 1:237--238, 1966.

\bibitem{cl:lov68}
L.~Lov\'{a}sz.
\newblock On the chromatic number of finite set systems.
\newblock {\em Acto. Math. Acad. Sci. Hungary}, 19:59--67, 1968.

\bibitem{cl:lst89}
Laszlo L\'{o}vasz, Michael Saks, and W.~T. Trotter.
\newblock An on-line graph coloring algorithm with sublinear performance ratio.
\newblock {\em Discrete Mathematics}, 75(1,3):319--325, 1989.

\bibitem{cl:luc91a}
Tomasz Luczak.
\newblock The chromatic number of random graphs.
\newblock {\em Combinatorica}, 11(1):45--54, 1991.

\bibitem{cl:luc91b}
Tomasz Luczak.
\newblock A note on the sharp concentration of the chromatic number of random
  graphs.
\newblock {\em Combinatorica}, 11(3):295--297, 1991.

\bibitem{cl:masa93}
Carlo Mannino and Antonio Sassano.
\newblock An exact algorithm for the maximum cardinality stable set problem.
\newblock {\em Networks}, page (submitted), 1993.
\newblock ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

\bibitem{cl:man81}
B.~Manvel.
\newblock Coloring large graphs.
\newblock {\em Proc. 12th Southeastern Conference on combinatorics, Graph
  Theory and Computing}, pages 197--204, 1981.

\bibitem{cl:man85}
Bennet Manvel.
\newblock Extremely greedy coloring algorithms.
\newblock In {\em Graphs and applications (Boulder, Colo., 1982)},
  Wiley-Intersci. Pub., pages 257--270, New York, New York, 1985. John Wiley \&
  Sons, Inc.

\bibitem{cl:mat68}
D.~W. Matula.
\newblock A min-max theorem for graphs with application to graph coloring.
\newblock {\em SIAM Review}, 10:481--482, 1968.

\bibitem{cl:mat72}
D.~W. Matula.
\newblock Bounded color functions on graphs.
\newblock {\em Networks}, 2:29--44, 1972.
\newblock NCPY.

\bibitem{cl:mat87}
D.~W. Matula.
\newblock Expose-and-merge exploration and the chromatic number of a random
  graph.
\newblock {\em Combinatorica}, 7(3):275--284, 1987.

\bibitem{cl:mabe83}
D.~W. Matula and L.~L. Beck.
\newblock Smallest-last ordering and clustering and graph coloring algorithms.
\newblock {\em Journal of the ACM}, 30(3):417--427, 1983.

\bibitem{cl:maku90}
David Matula and Lud\v{e}k Ku\v{c}era.
\newblock An expose-and-merge algorithm and the chromatic number of a random
  graph.
\newblock In M.~Karo\'{n}ski, J.~Jaworski, and A.~Rucii\'{n}ski, editors, {\em
  Random Graphs '87}, pages 175--187. John Wiley \& Sons, Inc., 1990.

\bibitem{cl:mmi72}
David~W. Matula, George Marble, and Joel~D. Isaacson.
\newblock Graph coloring algorithms.
\newblock In {\em Graph theory and computing}, pages 109--122. Academic Press,
  Inc., 1972.

\bibitem{cl:mcc83}
S.~T. McCormick.
\newblock Optimal approximation of sparse hessians and its equivalence to a
  graph coloring problem.
\newblock {\em Mathematical Programming}, 26(2):153--171, 1983.

\bibitem{cl:mcd79b}
C.~J.~H. McDiarmid.
\newblock Determining the chromatic number of a graph.
\newblock {\em SIAM Journal on Computing}, 8:1--14, 1979.

\bibitem{cl:mcd79a}
Colin McDiarmid.
\newblock Colouring random graphs badly.
\newblock In {\em Graph theory and combinatorics (Proc. Conf., Open Univ.,
  Milton Keynes, 1978)}, Res. Notes in Math. 34, pages 76--86. Pitman, San
  Francisco, Calif., 1979.

\bibitem{cl:mcd82}
Colin McDiarmid.
\newblock Achromatic numers of random graphs.
\newblock {\em Mathematical Proceedings of the Cambridge Philosophical
  Society}, 92:21--28, 1982.

\bibitem{cl:mcd83}
Colin McDiarmid.
\newblock On the chromatic forcing number of a random graph.
\newblock {\em Discrete Applied Mathematics}, 5:123--132, 1983.

\bibitem{cl:mcd84}
Colin McDiarmid.
\newblock Colouring random graphs.
\newblock {\em Annals of Operations Research}, 1:183--200, 1984.

\bibitem{cl:mil75}
D.~M. Miller.
\newblock An algorithm for determining the chromatic number of a graph.
\newblock In {\em Proceedings 5th Manitoba Conference on Numerical Math.}, page
  533, 1975.

\bibitem{cl:mit76}
J.~Mitchem.
\newblock On various algorithms for estimating the chromatic number of a graph.
\newblock {\em The Computer Journal}, 19:182, 1976.

\bibitem{cl:mosp85}
B.~Monien and E.~Speckenmeyer.
\newblock Ramsey numbers and an approximation algorithm for the vertex cover
  problem.
\newblock {\em Acta Informatica}, 22:115--123, 1985.
\newblock NCPY.

\bibitem{cl:momo65}
J.~W. Moon and L.~Moser.
\newblock On cliques in graphs.
\newblock {\em Israel Journal of Mathematics}, 3:23--28, 1965.

\bibitem{cl:muco72}
G.~D. Mulligan and D.~G. Corneil.
\newblock Corrections to bierstone's algorithm for generating cliques.
\newblock {\em Journal of the ACM}, 19(2):244--247, 1972.

\bibitem{cl:newi90}
Roy Nelson and Robin~J. Wilson, editors.
\newblock {\em Graph Colourings}.
\newblock Pitman Research notes in Mathematics. Longman Scientific and
  Technical, 1990.
\newblock A one day conference: survey papers.

\bibitem{cl:neta74}
G.~A. Neufeld and J.~Tartar.
\newblock Graphs coloring conditions for the existence of solutions to the
  timetable problem.
\newblock {\em Communications of the ACM}, 17:450--453, 1974.

\bibitem{cl:neta75}
G.~A. Neufeld and J.~Tartar.
\newblock Generalized graph colorations.
\newblock {\em SIAM Journal on Applied Mathematics}, 29:91--98, 1975.

\bibitem{cl:nera83}
Garry~N. Newsam and John~D. Ramsdell.
\newblock Estimation of sparse {J}acobian matrices.
\newblock {\em SIAM Journal on Algebraic and Discrete Methods}, 4(3):404--418,
  1983.

\bibitem{cl:nie74}
U.~J. Nieminen.
\newblock A viewpoint to the minimum coloring problem of hypergraphs.
\newblock {\em Kybernetika(Prague)}, 10:504--508, 1974.
\newblock MR vol. 51 p. 757.

\bibitem{cl:ola9x}
S.~Olariu.
\newblock All variations on perfectly orderable graphs.
\newblock {\em Journal of Combinatorial Theory Series B}, Unknown.
\newblock to appear.

\bibitem{cl:olra89}
Stephan Olariu and J.~Randall.
\newblock Welsh-{P}owell opposition graphs.
\newblock {\em Information Processing Letters}, 31(1):43--46, 1989.

\bibitem{cl:pasr92}
Alessandro Panconesi and Aravind Srinivasan.
\newblock Improved distributed algorithms for coloring and network
  decomposition problems.
\newblock In {\em Proceedings of the 24th Annual ACM Symposium on Theory of
  Computing}, pages 581--592, 1992.

\bibitem{cl:paya88}
Christos~H. Papadimitriou and Mihalis Yannakakis.
\newblock Optimization, approximation and complexity classes.
\newblock In {\em Proceedings of the Twentieth Annual ACM Symposium on Theory
  of Computing}, pages 229--234, 1988.

\bibitem{cl:paph90}
P.~M. Pardalos and A.~Phillips.
\newblock A global optimization approach for solving the maximum clique
  problem.
\newblock {\em International Journal of Computer Mathematics}, 33:209--216,
  1990.

\bibitem{cl:pade91}
P.M. Pardalos and Nisha Desai.
\newblock An algorithm for finding a maximum weighted independent set in an
  arbitrary graph.
\newblock {\em International Journal of Computer Mathematics}, 38:163--175,
  1991.

\bibitem{cl:paro92}
P.M. Pardalos and G.P. Rodgers.
\newblock A branch and bound algorithm for the maximum clique problem.
\newblock {\em Computers and Operations Research}, 19(5):363--376, July 1992.

\bibitem{cl:paxu93}
Panos~M. Pardlos and Jue Xue.
\newblock The maximum clique problem.
\newblock {\em Journal of Global Optimization}, page (to appear), 1993.
\newblock ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

\bibitem{cl:pee83}
Jurgen Peem\"{o}ller.
\newblock A correction to {B}r\'{e}laz's modification of {B}rown's coloring
  algorithm.
\newblock {\em Communications of the ACM}, 26(8):595--597, 1983.

\bibitem{cl:pee86}
Jurgen Peem\"{o}ller.
\newblock Numerical experiences with graph coloring algorithms.
\newblock {\em European Journal of Operational Research}, 24(1):146--151, 1986.
\newblock First EURO VI special issue.

\bibitem{cl:pro91}
Patrick Prosser.
\newblock Hybrid algorithms for the constraint satisfaction problem.
\newblock Research Report AISL-46-91, University of Strathclyde, Dept. of
  Computer Science, Univ. of Strathclyde, Livingstone Tower, 26 Richmond
  Street, Glasgow G1 1XH Scotland, September 1991.

\bibitem{cl:rob71}
J.~M. Robson.
\newblock An estimate of the store size necessary for dynamic storage
  allocation.
\newblock {\em Journal of the ACM}, 18:416--423, 1971.
\newblock Related to Online Graph Coloring.

\bibitem{cl:rut86}
V.~Rutenberg.
\newblock Complexity of generalized graph coloring.
\newblock In J.~Gruska, B.~Rovan, and J.~Wiedermann, editors, {\em Mathematical
  foundations of computer science 1986; Proceedings of the twelfth symposium
  held in Bratislava}, volume 233 of {\em Lecture Notes in Computer Science},
  pages 537--581. Springer-Verlag, August 1986.

\bibitem{cl:snh76}
T.~Sakaki, K.~Nakashima, and Y.~Hattori.
\newblock Algorithms for finding in lump both bounds of the chromatic number of
  a graph.
\newblock {\em The Computer Journal}, 19:329--332, 1976.

\bibitem{cl:saoa74}
A.~Salazar and R.~V. Oakford.
\newblock A graph formulation of a school scheduling algorithm.
\newblock {\em Communications of the ACM}, 18:241--242, 1974.
\newblock see Korfhage and Matula also Garey and Johnson.

\bibitem{cl:saba89}
S.~Sen Sarma and S.~K. Bandyopadhyay.
\newblock Some sequential graph colouring algorithms.
\newblock {\em International Journal of Electronics}, 67(2):187--199, 1989.

\bibitem{cl:scst80}
G.~Schmidt and T.~Str\"{o}hleim.
\newblock Timetable construction --- an annotated bibliography.
\newblock {\em The Computer Journal}, 23:307, 1980.

\bibitem{cl:sco76}
T.~B. Scott.
\newblock Graph colouring with preassignment and unavailability constraints.
\newblock {\em Ars Combinatoria}, 2:25--32, 1976.

\bibitem{cl:slm92}
Bart Selman, Hector Levesque, and David Mitchell.
\newblock A new method for solving hard satisfiability problems.
\newblock In {\em Proceedings of the Tenth National Conference on Artificial
  Intelligence (AAAI-92)}, pages 440--446, San Jose, Calif., 1992.

\bibitem{cl:shsp87}
E.~Shamir and J.~Spencer.
\newblock Sharp concentration of the chromatic number of random graphs
  {$G_{n,p}$}.
\newblock {\em Combinatorica}, 7:121--129, 1987.

\bibitem{cl:shup84}
Eli Shamir and Eli Upfal.
\newblock Sequential and distributed graph coloring algorithms with performance
  analysis in random graph spaces.
\newblock {\em Journal of Algorithms}, 5(4):488--501, 1984.

\bibitem{cl:shva89}
S.~Shuller and V.~V. Vazirani.
\newblock Planar graph coloring is not self-reducible assuming {P} not equal to
  {NP}.
\newblock Technical Report 89-1064, Cornell University, Department of Computer
  Science, 1989.
\newblock Subfile: STR (Stanford Technical Reports).

\bibitem{cl:sim85}
Gustavus~J. Simmons.
\newblock The {O}chromatic number of planar graphs.
\newblock In Frank Harary and John~S. Maybee, editors, {\em Graphs and
  Applications: Proceedigns of the First Colorado Symposium on Graph Theory},
  pages 295--316. John Wiley \& Sons, Inc., 1985.

\bibitem{cl:sim90}
Hans-Ulrich Simon.
\newblock On approximate solutions for combinatorial optimization problems.
\newblock {\em SIAM Journal on Discrete Mathematics}, 3(2):294--310, 1990.

\bibitem{cl:spvi85}
Jeremy~P. Spinrad and Gopalakrishnan Vijayan.
\newblock Worst case analysis of a graph coloring algorithm.
\newblock {\em Discrete Applied Mathematics}, 12(1):89--92, 1985.

\bibitem{cl:sto73}
L.~Stockmeyer.
\newblock Planar 3-colorability is polynomial complete.
\newblock {\em ACM SIGACT News}, 5(3):19--25, 1973.
\newblock NCPY.

\bibitem{cl:szwi68}
G.~Szekeres and H.~S. Wilf.
\newblock An inequality for the chromatic number of a graph.
\newblock {\em Journal of Combinatorial Theory}, 4:1--3, 1968.

\bibitem{cl:tar85}
Robert~E. Tarjan.
\newblock Decomposition by clique separators.
\newblock {\em Discrete Mathematics}, 55(2):221--232, 1985.

\bibitem{cl:tatr77}
Robert~Endre Tarjan and Anthony~E. Trojanowski.
\newblock Finding a maximum independent set.
\newblock {\em SIAM Journal on Applied Mathematics}, 6(3):537--546, 1977.

\bibitem{cl:thle81}
J.~Thepot and G.~Lechenault.
\newblock A note on an application of hierarchical clustering to graph
  coloring.
\newblock {\em RAIRO Rech. Oper.}, 15(1):73--83, 1981.
\newblock French.

\bibitem{cl:tom68}
I.~Tomescu.
\newblock Sur le probl\`{e}me du coloriage des graphes g\'{e}n\'{e}ralis\'{e}s.
\newblock {\em C. R. Acad. Sci. Paris Ser. A}, 267:250--252, 1968.

\bibitem{cl:tur54}
P.~Turan.
\newblock On the theory of graphs.
\newblock {\em Colloq. Math.}, 3:19--30, 1954.

\bibitem{cl:tur67}
J.~Turner.
\newblock Point symmetric graphs with a prime number of points.
\newblock {\em Journal of Combinatorial Theory}, 3:136--145, 1967.

\bibitem{cl:turn84}
J.~S. Turner.
\newblock On the probable performance of graph colouring algorithms.
\newblock In {\em Proceedings, 1984 Allerton Conference on Communications,
  Control and Computing}, pages 281--290, 1984.

\bibitem{cl:tur85}
J.~S. Turner.
\newblock On the probable performance of graph coloring algorithms.
\newblock Technical Report WUCS--85--7, (Washington University, Department of
  Computer Science, 1985.
\newblock Subfile: STR (Stanford Technical Reports).

\bibitem{cl:tur88}
Jonathan~S. Turner.
\newblock Almost all $k$-colorable graphs are easy to color.
\newblock {\em Journal of Algorithms}, 9:63--82, 1988.

\bibitem{cl:zer89}
Janez \u{Z}erovnik.
\newblock A randomised heuristical algorithm for estimating the chromatic
  number of a graph.
\newblock {\em Information Processing Letters}, 33:213--219, 1989.

\bibitem{cl:zer90}
Janez \u{Z}erovnik.
\newblock A parallel variant of a heuristical algorithm for graph coloring.
\newblock {\em Parallel Computing}, 13:95--100, 1990.

\bibitem{cl:vele88}
Ramarathnam Venkatesan and Leonid~A. Levin.
\newblock Random instances of a graph coloring problem are hard.
\newblock In {\em Proceedings of the Twentieth Annual ACM Symposium on Theory
  of Computing}, pages 217--222, 1988.

\bibitem{cl:vis90}
S.~Vishwanathan.
\newblock Randomized online graph coloring.
\newblock In {\em 31st Annual Symposium on Foundations of Computer Science},
  pages 464--469, 1990.

\bibitem{cl:wag80}
S.~Wagon.
\newblock A bound on the chromatic number of graphs without certain induced
  subgraphs.
\newblock {\em Journal of Combinatorial Theory Series B}, 29:345--346, 1980.

\bibitem{cl:wan74}
C.~C. Wang.
\newblock An algorithm for the chromatic number of a graph.
\newblock {\em Journal of the ACM}, 21:385, 1974.

\bibitem{cl:wepo67}
D.~J.~A. Welsh and M.~B. Powell.
\newblock An upper bound for the chromatic number of a graph and its
  applications to timetabling problems.
\newblock {\em The Computer Journal}, 10:85--86, 1967.

\bibitem{cl:wid82}
A.~Wigderson.
\newblock A new approximate graph coloring algorithm.
\newblock In {\em Proceedings of the Fourteenth Annual ACM Symposium on Theory
  of Computing}, pages 325--329, 1982.
\newblock NCPY.

\bibitem{cl:wig83}
Avi Wigderson.
\newblock Improving the performance guarantee for approximate graph coloring.
\newblock {\em Journal of the ACM}, 30(4):729--735, 1983.

\bibitem{cl:wil67}
H.~S. Wilf.
\newblock The eigenvalues of a graph and its chromatic number.
\newblock {\em J. London math. Soc.}, 42:330--332, 1967.

\bibitem{cl:wil84}
Herbert~S. Wilf.
\newblock Backtrack: an {$O(1)$} expected time algorithm for the graph coloring
  problem.
\newblock {\em Information Processing Letters}, 18(3):119--121, 1984.

\bibitem{cl:wil86}
Herbert~S. Wilf.
\newblock Spectral bounds for the clique and independence numbers of graphs.
\newblock {\em Journal of Combinatorial Theory Series B}, 40(1):113--117, 1986.

\bibitem{cl:wil70}
M.~R. Williams.
\newblock The colouring of very large graphs.
\newblock In R.~Guy et~al, editor, {\em Combinatorial structures and their
  applications}, pages 477--478. Gordon and Breach, 1970.

\bibitem{cl:woo68}
D.~C. Wood.
\newblock A system for computing university examination timetables.
\newblock {\em The Computer Journal}, 11:41--47, 1968.

\bibitem{cl:woo69}
D.~C. Wood.
\newblock A technique for coloring a graph applicable to large scale
  timetabling problems.
\newblock {\em The Computer Journal}, 12:317--319, 1969.

\bibitem{cl:wowi77}
D.~R. Woodall and Robin~J. Wilson.
\newblock The {A}ppel-{H}aken proof of the four color theorem.
\newblock volume~16 of {\em Lecture Notes in Mathematics}, pages 83--101.
  Pitman, 1977.
\newblock booktitle?

\bibitem{cl:yeh89}
S.~S.~W. Yeh.
\newblock Odd cycles, bipartite subgraphs, and approximate graph coloring.
\newblock Publ: Princeton University, Princeton, NJ, 1989.
\newblock UMI order no: GAX89-17763.

\bibitem{cl:you69}
J.~W.~T. Youngs.
\newblock Remarks on the four color problem.
\newblock In Richard Guy, Haim Hanani, Norbert Sauer, and Jonathan Schonheim,
  editors, {\em Combinatorial Structures and Their Applications: Proceedings of
  the Calagary International Conference on Combinatorial Structures and Their
  Applications}, pages 479--480. Gordon and Breach, 1969.

\bibitem{cl:zas82}
T.~Zaslavsky.
\newblock Signed graph coloring.
\newblock {\em Discrete Mathematics}, 39(2):215--228, 1982.

\bibitem{cl:zhu85}
Ao~Xin Zhu.
\newblock Non-coloring-contradiction graphs and a graph coloring algorithm.
\newblock {\em Chinese Journal of Computers}, 8(3):189--197, 1985.
\newblock chinese: English summary.

\bibitem{cl:zky52}
A.~A. Zykov.
\newblock On some properties of linear complexes.
\newblock {\em Mat. Sb.}, 24:163--188, 1949.
\newblock English Trans. Amer. Soc. Translation no. 79, 1952.

\end{thebibliography}