References

[1] A. V. Anisimov. Local optimization of graph coloring. Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskoi SSR. Kibernetika, (6):1–8,133, 1986. number or volume?

[2] K. Appel and W. Haken. Every planar map is four colorable: Part 1, discharging. Illinois Journal of Mathematics, 21:429–490, 1977.

[3] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable: Part 2, reducibility. Illinois Journal of Mathematics, 21:491–567, 1977.

[4] J. S. Appleby, D. V. Blake, and E. A. Newman. Techniques for producing school timetables on a computer and their application to other scheduling problems. The Computer Journal, 3:237–245, 1961.

[5] E. Arjomandi. An efficient algorithm for colouring the edges of a graph with delta + 1 colours. Technical Report 1, York University, Department of Computer Science, 1980. Subfile: STR (Stanford Technical Reports).

[6] Bengt Aspvall and John R. Gilbert. Graph coloring using eigenvalue decomposition. SIAM Journal on Algebraic and Discrete Methods, 5(4):526–538, 1984.

[7] G. Ausiello, A. D’Atri, and M. Protasi. Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences, 21:136–153, 1980.

[8] Egon Balas and Chang Sung Yu. Finding a maximum clique in an arbitrary graph. SIAM Journal on Computing, 15(4):1054–1068, 1986.

[9] Pierre Baldi and Edward C. Posner. Graph coloring bounds for cellular radio. Computers and Mathematics with Applications, 19(10):91–97, 1990.

[10] R. Bar-Yehuda and S. Even. A 2 − \frac{log log n}{2 log n} performance ratio for the weighted vertex cover problem. Technical Report #260, Technion Haifa, January 1983. NCPY.

[11] Edward A. Bender and Herbert S. Wilf. A theoretical analysis of backtracking in the graph coloring problem. Journal of Algorithms, 6(2):275–282, 1985.

[12] C. Berge and P. Duchet. Strongly perfect graphs. Annals of Discrete Mathematics, 21:57–61, 1984.

[13] Claude Berge. Algorithms and extremal problems for equipartite colorings in graphs and hypergraphs, volume 2 of Annals of Discrete Mathematics, pages 149–150. North-Holland Publishing Co., 1978.

[14] Bonnie Berger and John Rompel. A better performance guarantee for approximate graph coloring. Algorithmica, 5(4):459–466, 1990.

[15] J. R. Bitner and E. Reingold. Backtrack programming techniques. Communications of the ACM, 18:651–656, 1975.

[16] Avrim Blum. Some tools for approximate 3-coloring. In 31st Annual Symposium on Foundations of Computer Science, pages 554–562, 1990.

[17] Avrin Blum. An Õ(n^{0.4})-approximation algorithm for 3-coloring (and improved approximation algorithms for k-coloring). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 535–542, 1989.

[18] B. Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49–55, 1988.

[19] B. Bollobás and P. Erdös. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 80(41):419–427, 1976.

[20] Béla Bollobás. Chromatic number, girth and maximal degree. Discrete Mathematics, 24:311–314, 1978.

[21] Béla Bollobás and Andrew Thomason. Random graphs of small order. In Random Graphs ’83, volume 28 of Annals of Discrete Mathematics, pages 47–97. North-Holland Publishing Co., 1985. Section 6: “Colouring large random graphs”.

[22] J. A. Bondy. Bounds for the chromatic number of a graph. Journal of Combinatorial Theory, 7:96–98, 1969.

[23] Ravi Boppana and Magnus Halldorsson. Approximating maximum independent sets by excluding subgraphs. In SWAT 90 2nd Scandinavian Workshop on Algorithm Theory, volume 3 of Lecture Notes in Computer Science, pages 13–25, 1990.

[24] Joan F. Boyar and Howard J. Karloff. Coloring planar graphs in parallel. Journal of Algorithms, 8:470–479, 1987.

[25] Daniel Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, April 1979.

[26] Sol Broder. Final examination scheduling. Communications of the ACM, 7(8):494–498, August 1964.

[27] Coen Bron and Joep Kerbosch. Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9):575–577, 1973.

[28] R. L. Brooks. On coloring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37:194–197, 1941.

[29] J. Randall Brown. Chromatic scheduling and the chromatic number problem. Management Science, 19(4):456–463, 1972. Part I.

[30] Jason I. Brown, David kelly, J. Schonheim, and Robert E. Woodrow. Graph coloring satisfying restraints. Discrete Mathematics, 80(2):123– 143, 1990.

[31] E. Burattini, A. Massarotti, and A. Santaniello. A graph colouration technique. In Second International Conference on Information Sciences and Systems (Univ. Patras, Patras, 1979), Vol. III, pages 326–333. Reidel, 1980.

[32] Jane Cameron and Gomer Thomas. An approximate graph partitioning algorithm and its computational complexity. Congressus Numerantium, 49:287–293, 1985.

[33] G. Campers, O. Henkes, and J. P. Leclercq. Sur les methodes exactes de coloration de graphes. On exact methods of graph coloring. Cahiers du Centre d’Etudes de Recherche Operationnelle, 29(1–2):19–30, 1987.

[34] G. Campers, O. Henkes, and J. P. Leclerq. Graph coloring heuristics: a survey, some new propositions and computational experiences on random and “Leighton’s” graphs. In Operational research ’87 (Buenos Aires, 1987), pages 917–932. North-Holland Publishing Co., 1988.

[35] R. Carraghan and P. M. Pardalos. An exact algorithm for the maximum clique problem. Operations Research Letters, 9:375–382, 1990.

[36] Paul A. Catlin. Homomorphisms as a generalization of graph coloring. Congressus Numerantium, 50:179–186, 1985.

[37] M. Chams, A. Hertz, and D. de Werra. Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research, 32(2):260–266, 1987.

[38] Ya. I. Cheban. Investigation of a generalized graph coloring problem. In Investigation of methods for solving extremal problems (Russian), vii, pages 77–81. Akad. Nauk Ukrain. SSR, Inst. Kibernet., Kiev, 1986.

[39] Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Where the really hard problems are. In International Joint Conference on Artificial Intelligence, pages 331–337, 1991.

[40] M. Chorbak and M. Ślusarek. Problem 84-23. Journal of Algorithms, 5:588, 1984.

[41] N. Christofides. An algorithm for the chromatic number of a graph. Computing, 14:38–39, 1971.

[42] V. Chvátal. Perfectly ordered graphs. In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs, volume 21 of Annals of Discrete Mathematics. North-Holland Publishing Co., 1984.

[43] V. Chvátal, M. R. Garey, and D. S. Johnson. Two results concerning multicoloring. volume 2 of Annals of Discrete Mathematics, pages 151– 154. North-Holland Publishing Co., 1978. booktitle?

[44] V. Chvátal, C. T. Hoang, N. V. R. Mahadev, and D. de Werra. Four classes of perfectly orderable graphs. Journal of Graph Theory, 11:481– 495, 1987.

[45] A. J. Cole. The preparation of examination time-tables using a smallstore computer. The Computer Journal, 7:117–121, 1964.

[46] T. F. Coleman and J. J. More. Estimation of sparse jacobian matrices and graph coloring problems. SIAM Journal on Numerical Analysis, 20(1):187–209, 1983.

[47] Thomas F. Coleman and Jorge J. More. Estimation of sparse hessian matrices and graph coloring problems. Mathematical Programming, 28(3):243–270, 1984.

[48] R. J. Cook. Chromatic number and girth. Periodica Mathematica Hungarica, 6(1):103–107, 1975.

[49] D. G. Corneil and B. Graham. An algorithm for determining the chromatic number of a graph. SIAM Journal on Computing, 2(4):311–318, 1973.

[50] Joseph C. Culberson. Iterated greedy graph coloring and the difficulty landscape. Technical Report TR 92-07, University of Alberta Department of Computing Science, Edmonton, Alberta Canada T6G 2H1, 1992. ftp ftp.cs.ualberta.ca pub/TechReports.

[51] D. P. Dailey. Uniqueness of colorability and colorability of planar 4regular graphs are NP-complete. Discrete Mathematics, 30:289–293, 1980.

[52] W. Fernandex de la Vega. Random graphs almost optimally colorable in polynomial time. In Random Graphs ’83, volume 28 of Annals of Discrete Mathematics, pages 311–317. North-Holland Publishing Co., 1985.

[53] W. Fernandez de la Vega. On the chromatic number of sparse random graphs. In B. Bollobás, editor, Graph theory and combinatorics, Proceedings Cambridge combinatorial conference in hobour of Paul Erdös, pages 321–328. Academic Press, Inc., 1984.

[54] D. de Werra. How to color a graph. In B. Roy, editor, Combinatorial Programming — Methods and Applications, pages 305–325. NATO Advanced Science Institute Series C: Mathematical and Physical Sciences, 1974. Vol. 19.

[55] D. de Werra. Some results in chromatic scheduling. Z. operations Res. Ser. A, 16:167–175, 1974.

[56] D. de Werra. On a particular conference scheduling problem. INFOR— Canadian Journal of Operational Research and Information Processing, 13:308–315, 1975.

[57] Peter Dencker, Karl Durre, and Johannes Heuft. Optimization of parser tables for portable compilers. ACM Transactions on Programming Languages and Systems, 6(4):546–572, 1984.

[58] Blanches Descartes. A three colour problem. Eureka, April 1947. solution march 1948; pseudonym for Tutte.

[59] Blanches Descartes. Solution to advanced problem 4526. The American Mathematical Monthly, 61:352, 1954. proposed by P. Ungar; psuedonym for Tutte.

[60] Krzysztof Diks. A fast parallel algorithm for six-colouring of planar graphs (extended abstract). In J. Gruska, B. Rovan, and J. Wiedermann, editors, Mathematical foundations of computer science 1986; Proceedings of the twelfth symposium held in Bratislava, volume 233 of Lecture Notes in Computer Science, pages 273–282. Springer-Verlag, 1986.

[61] G. A. Dirac. The structure of k-chromatic graphs. Fundamenta Mathematicae, 40:42–55, 1953. color.

[62] F. D. J. Dunstan. Sequential colourings of graphs. In Proceedings of Fifth British Combinatorial Conference, pages 151–158. Utilitas Mathematica, 1976.

[63] K. Dürre. An algorithm for coloring the vertices of an arbitrary graph. In P. Deussen, editor, unknown, volume 78 of Lecture Notes in Economics and Mathematical Systems, pages 82–89. Springer-Verlag, 1973.

[64] K. Dürre, J. Heuft, and H. Muller. Worst and best case behaviour of an approximate graph coloring algorithm. In J. R. Muhlbacher and Carl Hansen Verlag, editors, Proc. 7th conference on graphtheoretic concepts in computer science (Linz, Austria, June 15-17, 1981), pages 339–348, Munich, 1982.

[65] R. D. Dutton and R. C. Brigham. A new graph coloring algorithm. The Computer Journal, 24(1):85–86, 1981.

[66] M. E. Dyer and A. M. Frieze. Fast solution of some random NP-hard problems. In 27th Annual Symposium on Foundations of Computer Science, pages 331–336, 1986.

[67] M. E. Dyer and A. M. Frieze. The solution of some random NP-hard problems in polynomial expected time. Journal of Algorithms, 10:451– 489, 1989.

[68] S. Early. Evaluating a Timetabling Algorithm Based on Graph Recolouring. PhD thesis, University of Oxford, 1968. B. Phil. Diss.

[69] J. A. Ellis and P. M. Lepolesa. A Las Vegas coloring algorithm. The Computer Journal, 32(5):474–476, 1989.

[70] P. Erdös. Graph theory and probability. Canadian Journal of Mathematics, 11:34–38, 1959.

[71] P. Erdös and R. J. Wilson. On the chromatic index of almost all graphs. Journal of Combinatorial Theory Series B, 23:255–257, 1977.

[72] Marcel Erne and Paul Erdös. Clique numbers of graphs. Discrete Mathematics, 59(3):235–241, 1986.

[73] Feder and Motwani. Clique partitions, graph compression and speeding up algorithms. In Proceedings of the Twenty Third Annual Symposium on Theory of Computing, pages 123–3, 1991.

[74] U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. In 32nd Annual Symposium on Foundations of Computer Science, pages 2–3, 1991.

[75] Stanley Fiorini and Robin J. Wilson. Edge-colorings of graphs. volume 16 of Lecture Notes in Mathematics, pages 102–126. Pitman, 1977. booktitle?

[76] J. A. Formby. A computer procedure for bounding the chromatic number of a graph. In D. J. A. Welsh, editor, Combinatorial Mathematics and its Applications, pages 111–114, Proceedings of a Conference in Oxford, July 1969. Academic Press, Inc.

[77] E. C. Freuder. A sufficient condition of backtrack-free search. Journal of the ACM, 29(1):24–32, 1982.

[78] C. Friden, A. Hertz, and D. de Werra. STABULUS: A technique for finding stable sets in large graphs with tabu search. Computing, 42:35– 44, 1989.

[79] Alan M. Frieze. On the independence number of random graphs. Discrete Mathematics, 81:171–175, 1990.

[80] Alan M. Frieze. Parallel colouring of random graphs. In M. Karoński, J. Jaworski, and A. Rudiński, editors, Random Graphs ’87, pages 41– 52. John Wiley & Sons, Inc., 1990.

[81] Martin Fürer and C. R. Subramanian. Coloring random graphs. In The Third Scandinavian Workshop on Algorithm Theory (SWAT ’92), 1992. preprint.

[82] Harold N. Gabow and Oded Kariv. Algorithms for edge coloring bipartite graphs and multigraphs. SIAM Journal on Computing, 11(1):117– 129, 1982.

[83] M. R. Garey and D. S. Johnson. On Salazar and Oakford. Communications of the ACM, 18:240–241, 1975.

[84] M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. Journal of the ACM, 23:43–49, 1976.

[85] M. R. Garey, D. S. Johnson, and I. Stockmeyer. Some simplified NPcomplete graph problems. Theoretical Computer Science, 1:237–267, 1976.

[86] Fǎnicǎ Gavril. Algorithms for coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Applied Mathematics, 1(2):181–187, 1972.

[87] L. Gerhards and W. Lindenberg. Clique detection for nondirected graphs. Computing, 21:295–322, 1979.

[88] Mario Gionfriddo. A short survey of some generalized colourings of graphs. Ars Combinatoria, 24(B):155–163, 1987.

[89] F. Glover. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13:533–549, 1986.

[90] S. W. Golomb and L. D. Baumert. Backtrack programming. Journal of the ACM, 12:516–524, 1965.

[91] Jerrold R. Griggs. Lower bounds on the independence number in terms of the degrees. Journal of Combinatorial Theory Series B, 34:22–39, 1983.

[92] G. R. Grimmett and C. J. H. McDiarmid. On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 77:313–324, 1975.

[93] B. Grünbaum. A problem in graph colouring. The American Mathematical Monthly, 77:1088–1092, 1970.

[94] A. Gyárfás. Problems from the world surrounding perfect graphs. Research Report 177, Computer and Automation Institute Studies, 1985.

[95] A. Gyarfas and J. Lehel. On-line and first fit colorings of graphs. Journal of Graph Theory, 12(2):217–227, 1988.

[96] András Gyárfás and Jenö Lehel. Online coloring of p_{5}-free graphs. Combinatorica, 11(2):181–184, 1991.

[97] Jonas Hasselberg, Panos M. Pardalos, and George Vairaktarakis. Test case generators and computational results for the maximum clique problem. ftp dimacs.rutgers.edu pub/challenge/graph/contributed, 1992. Working Paper.

[98] Bruce Hedman. The maximum number of cliques in dense graphs. Discrete Mathematics, 54(2):161–166, 1985.

[99] P. Hell and D. G. Kirkpatrick. Scheduling, matching, and coloring. In Algebraic methods in graph theory, Vol. I, II, Colloq. Math. Soc. Janos Bolyai, 25, pages 273–279. North-Holland Publishing Co., 1981.

[100] A. Hertz and D. de Werra. Using tabu search techniques for graph coloring. Computing, 39(4):345–351, 1987.

[101] A. J. W. Hilton, R. Rado, and S. H. Scott. A (< 5)-color theorem for planar graphs. Bull. London Math. Soc., 5:302–306, 1973. NCPY.

[102] A. J. W. Hilton and Robin J. Wilson. Edge colorings of graphs: A progress report. In Graph Theory and its Applications East and West: Proceedings of the First China-USA International Graph Theory Conference, volume 576 of Annals of the New York Academy of Sciences, pages 241–249, 1989.

[103] Cornelis Hoede. Hard graphs for the maximum clique problem. Discrete Mathematics, 72(1–3):175–179, 1988.

[104] P. Holgate. Majorants of the chromatic number of a random graph. J. Roy. Statist. Soc. Ser. B., 31:303–309, 1969.

[105] Glenn Hopkins and William Staton. Graphs with unique maximum independent sets. Discrete Mathematics, 57(3):245–251, 1985.

[106] Sandy Irani. Coloring inductive graphs on-line. In 31st Annual Symposium on Foundations of Computer Science, pages 470–479, 1990.

[107] Arun Jagota. Efficiently approximating max-clique in a hopfield-style network. In Proceedings of International Joint Conference on Neural Networks ’92 Volume II, pages 248–253, 1992. ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

[108] Arun Jagota and Kenneth W. Regan. Performance of max-clique approximation heuristics under description-length weighted distributions. Technical report, Department of Computer Science, State University at New York at Buffalo, 1992. ftp ftp.cs.buffalo.edu users/jagota or ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

[109] Garry Johns and Farrokh Saba. On the path-chromatic number of a graph. In Graph Theory and its Applications East and West: Proceedings of the First China-USA International Graph Theory Conference, volume 576 of Annals of the New York Academy of Sciences, pages 275–280, 1989.

[110] D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256–278, 1974.

[111] D. S. Johnson. Worst-case behavior of graph-coloring algorithms. In Proceedings of 5th Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 513–528, Winnipeg, 1974. Utilitas Mathematica.

[112] D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27:119– 123, 1988.

[113] David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon. Optimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning. Operations Research, 39(3):378–406, may-june 1991.

[114] A. Johri and D. W. Matula. Probabilistic bounds and heuristic algorithms. Technical Report 82-CSE-06, Southern Methodist University, Department of Computer Science, 1982. Supposed to have appeared?

[115] Viggo Kann. On the approximability of the maximum common subgraph problem. In STACS 92, pages 377–388, 1992.

[116] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–104. Plennum Press, New York, 1972. NCPY.

[117] Tsuyoshi Kawaguchi, Hideo Nakano, and Yoshiro Nakanishi. Probabilistic analysis of a heuristic graph coloring algorithm. Electron. Comm. Japan, 65(6):12–18, 1982.

[118] J. B. Kelly and L. M. Kelly. Paths and circuits in critical graphs. American Journal of Mathematics, 76:786–792, 1954. theory graph coloring.

[119] E. M. Kheifets. Planning of operation of communications links in packet radio networks using a graph-coloring algorithm. Automatic Control and Computer Sciences, 22(5):34–37, 1988.

[120] Samir Khuller. Coloring algorithms for k_{5}-minor free graphs. Information Processing Letters, 34:203–208, 1990.

[121] Samir Khuller. Extending planar graph algorithms to k_{3,3}-free graphs. Information and Computation, 84(1):13–25, 1990.

[122] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–679, May 1983.

[123] R. R. Korfhage and D. W. Matula. On S and O; more on the Salazar and Oakford paper. Communications of the ACM, 18:240,303, 1975.

[124] S. M. Korman. the graph-colouring problem. In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization, pages 211–235. John Wiley & Sons, Inc., 1979.

[125] A. D. Korshunov. The chromatic number of n-vertex graphs. Diskret. Analiz, 35:15–44, 1980. in Russian.

[126] M. Kubale and E. Kusz. Computer experiences with implicit enumeration algorithms for graph coloring. In M. Nagl and J. Perl, editors, International workshop on graphtheoretic concepts in computer science. Proceedings of the WG ’83, pages 167–176, Linz, Austria, 1983. Universitatsverlag Rudolf Trauner. GCL (ACM Guide to Computing Literature) ACM.

[127] Marek Kubale and Boguslaw Jackowski. A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, 28(4):412–418, 1985.

[128] Ludĕk Kuc̆era. Expected behavior of graph coloring algorithms. In FCT ’77, volume 56 of Lecture Notes in Computer Science, pages 447– 451. Springer-Verlag, Berlin, 1977.

[129] Ludĕk Kuc̆era. Graphs with small chromatic numbers are easy to color. Information Processing Letters, 30:233–236, 1989.

[130] Ludĕk Kuc̆era. A generalized encryption scheme based on random graphs. In 17th Annual Workshop on Graph-Theoretic Concepts in Computer Science (WG91), volume 570 of Lecture Notes in Computer Science, pages 180–186. Springer-Verlag, Berlin, 1991.

[131] E. L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5:66–67, year? full reference.

[132] F. T. Leighton. A graph colouring algorithm for large scheduling problems. J. Res. Nat. Bur. Stand., 84:489–496, 1979.

[133] N. Linial and U. Vazirani. Graph products and chromatic numbers. In 30th Annual Symposium on Foundations of Computer Science, pages 124–128, 1989.

[134] Nathan Linial. Graph coloring and monotone functions on posets. Discrete Mathematics, 58(1):97–98, 1986.

[135] Richard Lipton and Robert Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36:346–358, 1979.

[136] Richard Lipton and Robert Tarjan. Applications of a planar separator theorem. SIAM Journal on Computing, 9(3):615–626, 1980.

[137] Vahid Lotfi and Sanjiv Sarin. A graph coloring algorithm for large scale scheduling problems. Computers and Operations Research, 13(1):27– 32, 1986.

[138] E. Loukakis. A new backtracking algorithm for generating the family of maximal independent sets of a graph. Computers and Mathematics with Applications, 9:583–589, 1983.

[139] E. Loukakis and C. Tsouros. Determining the number of internal stability of a graph. International Journal of Computer Mathematics, 11:207–220, 1982.

[140] L. lovász. On decomposition of graphs. Studia Sci. Math. Hungar., 1:237–238, 1966.

[141] L. Lovász. On the chromatic number of finite set systems. Acto. Math. Acad. Sci. Hungary, 19:59–67, 1968.

[142] Laszlo Lóvasz, Michael Saks, and W. T. Trotter. An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics, 75(1,3):319–325, 1989.

[143] Tomasz Luczak. The chromatic number of random graphs. Combinatorica, 11(1):45–54, 1991.

[144] Tomasz Luczak. A note on the sharp concentration of the chromatic number of random graphs. Combinatorica, 11(3):295–297, 1991.

[145] Carlo Mannino and Antonio Sassano. An exact algorithm for the maximum cardinality stable set problem. Networks, page (submitted), 1993. ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

[146] B. Manvel. Coloring large graphs. Proc. 12th Southeastern Conference on combinatorics, Graph Theory and Computing, pages 197–204, 1981.

[147] Bennet Manvel. Extremely greedy coloring algorithms. In Graphs and applications (Boulder, Colo., 1982), Wiley-Intersci. Pub., pages 257– 270, New York, New York, 1985. John Wiley & Sons, Inc.

[148] D. W. Matula. A min-max theorem for graphs with application to graph coloring. SIAM Review, 10:481–482, 1968.

[149] D. W. Matula. Bounded color functions on graphs. Networks, 2:29–44, 1972. NCPY.

[150] D. W. Matula. Expose-and-merge exploration and the chromatic number of a random graph. Combinatorica, 7(3):275–284, 1987.

[151] D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417–427, 1983.

[152] David Matula and Luděk Kučera. An expose-and-merge algorithm and the chromatic number of a random graph. In M. Karoński, J. Jaworski, and A. Ruciiński, editors, Random Graphs ’87, pages 175–187. John Wiley & Sons, Inc., 1990.

[153] David W. Matula, George Marble, and Joel D. Isaacson. Graph coloring algorithms. In Graph theory and computing, pages 109–122. Academic Press, Inc., 1972.

[154] S. T. McCormick. Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Mathematical Programming, 26(2):153–171, 1983.

[155] C. J. H. McDiarmid. Determining the chromatic number of a graph. SIAM Journal on Computing, 8:1–14, 1979.

[156] Colin McDiarmid. Colouring random graphs badly. In Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), Res. Notes in Math. 34, pages 76–86. Pitman, San Francisco, Calif., 1979.

[157] Colin McDiarmid. Achromatic numers of random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 92:21–28, 1982.

[158] Colin McDiarmid. On the chromatic forcing number of a random graph. Discrete Applied Mathematics, 5:123–132, 1983.

[159] Colin McDiarmid. Colouring random graphs. Annals of Operations Research, 1:183–200, 1984.

[160] D. M. Miller. An algorithm for determining the chromatic number of a graph. In Proceedings 5th Manitoba Conference on Numerical Math., page 533, 1975.

[161] J. Mitchem. On various algorithms for estimating the chromatic number of a graph. The Computer Journal, 19:182, 1976.

[162] B. Monien and E. Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica, 22:115–123, 1985. NCPY.

[163] J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23–28, 1965.

[164] G. D. Mulligan and D. G. Corneil. Corrections to bierstone’s algorithm for generating cliques. Journal of the ACM, 19(2):244–247, 1972.

[165] Roy Nelson and Robin J. Wilson, editors. Graph Colourings. Pitman Research notes in Mathematics. Longman Scientific and Technical, 1990. A one day conference: survey papers.

[166] G. A. Neufeld and J. Tartar. Graphs coloring conditions for the existence of solutions to the timetable problem. Communications of the ACM, 17:450–453, 1974.

[167] G. A. Neufeld and J. Tartar. Generalized graph colorations. SIAM Journal on Applied Mathematics, 29:91–98, 1975.

[168] Garry N. Newsam and John D. Ramsdell. Estimation of sparse Jacobian matrices. SIAM Journal on Algebraic and Discrete Methods, 4(3):404–418, 1983.

[169] U. J. Nieminen. A viewpoint to the minimum coloring problem of hypergraphs. Kybernetika(Prague), 10:504–508, 1974. MR vol. 51 p. 757.

[170] S. Olariu. All variations on perfectly orderable graphs. Journal of Combinatorial Theory Series B, Unknown. to appear.

[171] Stephan Olariu and J. Randall. Welsh-Powell opposition graphs. Information Processing Letters, 31(1):43–46, 1989.

[172] Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 581–592, 1992.

[173] Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation and complexity classes. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 229–234, 1988.

[174] P. M. Pardalos and A. Phillips. A global optimization approach for solving the maximum clique problem. International Journal of Computer Mathematics, 33:209–216, 1990.

[175] P.M. Pardalos and Nisha Desai. An algorithm for finding a maximum weighted independent set in an arbitrary graph. International Journal of Computer Mathematics, 38:163–175, 1991.

[176] P.M. Pardalos and G.P. Rodgers. A branch and bound algorithm for the maximum clique problem. Computers and Operations Research, 19(5):363–376, July 1992.

[177] Panos M. Pardlos and Jue Xue. The maximum clique problem. Journal of Global Optimization, page (to appear), 1993. ftp dimacs.rutgers.edu pub/challenge/graph/contributed.

[178] Jurgen Peemöller. A correction to Brélaz’s modification of Brown’s coloring algorithm. Communications of the ACM, 26(8):595–597, 1983.

[179] Jurgen Peemöller. Numerical experiences with graph coloring algorithms. European Journal of Operational Research, 24(1):146–151, 1986. First EURO VI special issue.

[180] Patrick Prosser. Hybrid algorithms for the constraint satisfaction problem. 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.

[181] J. M. Robson. An estimate of the store size necessary for dynamic storage allocation. Journal of the ACM, 18:416–423, 1971. Related to Online Graph Coloring.

[182] V. Rutenberg. Complexity of generalized graph coloring. In J. Gruska, B. Rovan, and J. Wiedermann, editors, Mathematical foundations of computer science 1986; Proceedings of the twelfth symposium held in Bratislava, volume 233 of Lecture Notes in Computer Science, pages 537–581. Springer-Verlag, August 1986.

[183] T. Sakaki, K. Nakashima, and Y. Hattori. Algorithms for finding in lump both bounds of the chromatic number of a graph. The Computer Journal, 19:329–332, 1976.

[184] A. Salazar and R. V. Oakford. A graph formulation of a school scheduling algorithm. Communications of the ACM, 18:241–242, 1974. see Korfhage and Matula also Garey and Johnson.

[185] S. Sen Sarma and S. K. Bandyopadhyay. Some sequential graph colouring algorithms. International Journal of Electronics, 67(2):187–199, 1989.

[186] G. Schmidt and T. Ströhleim. Timetable construction — an annotated bibliography. The Computer Journal, 23:307, 1980.

[187] T. B. Scott. Graph colouring with preassignment and unavailability constraints. Ars Combinatoria, 2:25–32, 1976.

[188] Bart Selman, Hector Levesque, and David Mitchell. A new method for solving hard satisfiability problems. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 440– 446, San Jose, Calif., 1992.

[189] E. Shamir and J. Spencer. Sharp concentration of the chromatic number of random graphs G_{n,p}. Combinatorica, 7:121–129, 1987.

[190] Eli Shamir and Eli Upfal. Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces. Journal of Algorithms, 5(4):488–501, 1984.

[191] S. Shuller and V. V. Vazirani. Planar graph coloring is not self-reducible assuming P not equal to NP. Technical Report 89-1064, Cornell University, Department of Computer Science, 1989. Subfile: STR (Stanford Technical Reports).

[192] Gustavus J. Simmons. The Ochromatic number of planar graphs. In Frank Harary and John S. Maybee, editors, Graphs and Applications: Proceedigns of the First Colorado Symposium on Graph Theory, pages 295–316. John Wiley & Sons, Inc., 1985.

[193] Hans-Ulrich Simon. On approximate solutions for combinatorial optimization problems. SIAM Journal on Discrete Mathematics, 3(2):294– 310, 1990.

[194] Jeremy P. Spinrad and Gopalakrishnan Vijayan. Worst case analysis of a graph coloring algorithm. Discrete Applied Mathematics, 12(1):89– 92, 1985.

[195] L. Stockmeyer. Planar 3-colorability is polynomial complete. ACM SIGACT News, 5(3):19–25, 1973. NCPY.

[196] G. Szekeres and H. S. Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4:1–3, 1968.

[197] Robert E. Tarjan. Decomposition by clique separators. Discrete Mathematics, 55(2):221–232, 1985.

[198] Robert Endre Tarjan and Anthony E. Trojanowski. Finding a maximum independent set. SIAM Journal on Applied Mathematics, 6(3):537–546, 1977.

[199] J. Thepot and G. Lechenault. A note on an application of hierarchical clustering to graph coloring. RAIRO Rech. Oper., 15(1):73–83, 1981. French.

[200] I. Tomescu. Sur le problème du coloriage des graphes généralisés. C. R. Acad. Sci. Paris Ser. A, 267:250–252, 1968.

[201] P. Turan. On the theory of graphs. Colloq. Math., 3:19–30, 1954.

[202] J. Turner. Point symmetric graphs with a prime number of points. Journal of Combinatorial Theory, 3:136–145, 1967.

[203] J. S. Turner. On the probable performance of graph colouring algorithms. In Proceedings, 1984 Allerton Conference on Communications, Control and Computing, pages 281–290, 1984.

[204] J. S. Turner. On the probable performance of graph coloring algorithms. Technical Report WUCS–85–7, (Washington University, Department of Computer Science, 1985. Subfile: STR (Stanford Technical Reports).

[205] Jonathan S. Turner. Almost all k-colorable graphs are easy to color. Journal of Algorithms, 9:63–82, 1988.

[206] Janez Z̆erovnik. A randomised heuristical algorithm for estimating the chromatic number of a graph. Information Processing Letters, 33:213– 219, 1989.

[207] Janez Z̆erovnik. A parallel variant of a heuristical algorithm for graph coloring. Parallel Computing, 13:95–100, 1990.

[208] Ramarathnam Venkatesan and Leonid A. Levin. Random instances of a graph coloring problem are hard. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 217–222, 1988.

[209] S. Vishwanathan. Randomized online graph coloring. In 31st Annual Symposium on Foundations of Computer Science, pages 464–469, 1990.

[210] S. Wagon. A bound on the chromatic number of graphs without certain induced subgraphs. Journal of Combinatorial Theory Series B, 29:345– 346, 1980.

[211] C. C. Wang. An algorithm for the chromatic number of a graph. Journal of the ACM, 21:385, 1974.

[212] D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its applications to timetabling problems. The Computer Journal, 10:85–86, 1967.

[213] A. Wigderson. A new approximate graph coloring algorithm. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 325–329, 1982. NCPY.

[214] Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729–735, 1983.

[215] H. S. Wilf. The eigenvalues of a graph and its chromatic number. J. London math. Soc., 42:330–332, 1967.

[216] Herbert S. Wilf. Backtrack: an O(1) expected time algorithm for the graph coloring problem. Information Processing Letters, 18(3):119–121, 1984.

[217] Herbert S. Wilf. Spectral bounds for the clique and independence numbers of graphs. Journal of Combinatorial Theory Series B, 40(1):113– 117, 1986.

[218] M. R. Williams. The colouring of very large graphs. In R. Guy et al, editor, Combinatorial structures and their applications, pages 477–478. Gordon and Breach, 1970.

[219] D. C. Wood. A system for computing university examination timetables. The Computer Journal, 11:41–47, 1968.

[220] D. C. Wood. A technique for coloring a graph applicable to large scale timetabling problems. The Computer Journal, 12:317–319, 1969.

[221] D. R. Woodall and Robin J. Wilson. The Appel-Haken proof of the four color theorem. volume 16 of Lecture Notes in Mathematics, pages 83–101. Pitman, 1977. booktitle?

[222] S. S. W. Yeh. Odd cycles, bipartite subgraphs, and approximate graph coloring. Publ: Princeton University, Princeton, NJ, 1989. UMI order no: GAX89-17763.

[223] J. W. T. Youngs. Remarks on the four color problem. In Richard Guy, Haim Hanani, Norbert Sauer, and Jonathan Schonheim, editors, Combinatorial Structures and Their Applications: Proceedings of the Calagary International Conference on Combinatorial Structures and Their Applications, pages 479–480. Gordon and Breach, 1969.

[224] T. Zaslavsky. Signed graph coloring. Discrete Mathematics, 39(2):215– 228, 1982.

[225] Ao Xin Zhu. Non-coloring-contradiction graphs and a graph coloring algorithm. Chinese Journal of Computers, 8(3):189–197, 1985. chinese: English summary.

[226] A. A. Zykov. On some properties of linear complexes. Mat. Sb., 24:163– 188, 1949. English Trans. Amer. Soc. Translation no. 79, 1952.