Bibliography on Graph-Vertex Coloring

maintained by
Marco Chiarandini and Stefano Gualandi


The articles included in this bibliography focus on the problem of coloring the vertices of large and general graphs.
Publications are organized in the following categories.

If opportune a publication may appear in more than one category. Entries follow a reverse date order. The list does not aim to be exhaustive.
Last update: 12:59:48, November 12, 2015


Exact Methods

[GM12] S. Gualandi, F. Malucelli (2012). Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation. INFORMS Journal on Computing, vol. 24, no. 1, pp. 81-100. [ bib | DOI ]
[HCS12] S. Held, W. Cook, E. Sewell (2012). Maximum-weight stable sets and safe lower bounds for graph coloring. Mathematical Programming Computation, vol. 4, no. 4, pp. 363-381. [ bib | DOI | http ]
[HCS11] S. Held, W. Cook, E. Sewell (2011). Safe lower bounds for graph coloring. Integer Programming and Combinatoral Optimization, pp. 261-273. [ bib ]
[MMT11] E. Malaguti, M. Monaci, P. Toth (2011). An Exact Approach for the Vertex Coloring Problem. Discrete Optimization, vol. 8, no. 2, pp. 174-190. [ bib ]
[HLS09] P. Hansen, M. Labbé, D. Schindl (2009). Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discrete Optimization, vol. 6, no. 2, pp. 135 - 147. Also as Tec. Rep. G-2005-76 Cahier du GERAD, Montreal. [ bib | DOI | .html ]
[DGH08] C. Desrosiers, P. Galinier, A. Hertz (2008). Efficient algorithms for finding critical subgraphs. Discrete Applied Mathematics, vol. 156, no. 2, pp. 244-266. [ bib | DOI ]
[Gua08] S. Gualandi (2008). Enhancing Constraint Programming-based Column Generation for Integer Programs. Ph.D. thesis, Dipartimento di Elettronica e Informazione, Politecnico di Milano. [ bib ]
[MDZ08] I. Méndez-Díaz, P. Zabala (2008). A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, vol. 156, no. 2, pp. 159-179. [ bib | DOI ]
[BMPR07] E. K. Burke, J. Mareček, A. J. Parkes, H. Rudová (2007). On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling. Tech. Rep. NOTTCS-TR-2007-10, The University of Nottingham, Nottingham. [ bib | http ]
[LMM06] C. Lucet, F. Mendes, A. Moukrim (2006). An exact method for graph coloring. Computers & Operations Research, vol. 33, no. 8, pp. 2189-2207. [ bib | DOI ]
[MDZ06] I. Méndez-Díaz, P. Zabala (2006). A Branch-and-Cut algorithm for graph coloring. Discrete Applied Mathematics, vol. 154, no. 5, pp. 826-847. [ bib | DOI ]
[CD04] M. Caramia, P. Dell'Olmo (2004). Bounding vertex coloring by truncated multistage branch and bound. Networks, vol. 44, no. 4, pp. 231-242. [ bib | DOI ]
[Vas04] M. Vasquez (2004). New Results on the Queens_n2 Graph Coloring Problem. Journal of Heuristics, vol. 10, no. 4, pp. 407-413. [ bib | DOI ]
[Sch03] D. Schindl (2003). Graph coloring and linear programming. Presentation at First Joint Operations Research Days, Ecole Polytechnique Fédérale de Lausanne (EPFL), available on line (last visited June 2005). [ bib | .html ]
[Epp03] D. Eppstein (2003). Small Maximal Independent Sets and Faster Exact Graph Coloring. Journal of Graph Algorithms and Applications, vol. 7, no. 2, pp. 131-140. [ bib ]
[BB02] N. Barnier, P. Brisset (2002). Graph Coloring for Air Traffic Flow Management. In CPAIOR'02: Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems, pp. 133-147. Le Croisic, France. [ bib ]
[Gel02] A. V. Gelder (2002). Another Look at Graph Coloring via Propositional Satisfiability. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 48-54. Ithaca, New York, USA. [ bib ]
[GS02] C. Gomes, D. Shmoys (2002). Completing Quasigroups or Latin Squares: A Structured Graph Coloring Problem. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 22-39. Ithaca, New York, USA. [ bib ]
[HH02] F. Herrmann, A. Hertz (2002). Finding the chromatic number by means of critical graphs. Journal of Experimental Algorithmics, vol. 7, p. 10. [ bib | DOI ]
[CMMDZ02] P. Coll, J. Marenco, I. Mendez-Diaz, P. Zabala (2002). Facets of the Graph Coloring Polytope. Annals of Operations Research, vol. 116, no. 12, pp. 79-90. [ bib ]
[CD01] M. Caramia, P. Dell'Olmo (2001). Solving the minimum-weighted coloring problem. Networks, vol. 38, no. 2, pp. 88-101. [ bib ]
[MDZ01] I. Méndez-Díaz, P. Zabala (2001). A polyhedral approach for graph coloring. In Electronics Notes in Discrete Mathematics, vol. 7. springer. [ bib ]
[Sew96] E. Sewell (1996). An Improved Algorithm for Exact Graph Coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 359-373. American Mathematical Society, Providence, RI, USA. [ bib ]
[MT96] A. Mehrotra, M. Trick (1996). A Column Generation Approach for Graph Coloring. INFORMS Journal On Computing, vol. 8, no. 4, pp. 344-354. [ bib ]
[KJ85] M. Kubale, B. Jackowski (1985). A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, vol. 28, no. 4, pp. 412-418. [ bib | DOI ]
[Pee83] J. Peemöller (1983). A correction to Brelaz's modification of Brown's coloring algorithm. Communications of the ACM archive, vol. 26, no. 8, pp. 595-597. [ bib ]
[Bré79] D. Brélaz (1979). New Methods to Color the Vertices of a Graph. Communications of the ACM, vol. 22, no. 4, pp. 251-256. [ bib ]
[CG73] D. G. Corneil, B. Graham (1973). An Algorithm for Determining the Chromatic Number of a Graph. SIAM Journal on Computing, vol. 2, no. 4, pp. 311-318. [ bib ]
[Bro72] J. R. Brown (1972). Chromatic Scheduling and the Chromatic Number Problem. Management Science, vol. 19, no. 4, pp. 456-463. [ bib | http ]
[Mar] J. Marecek. [ bib | http ]



Construction Heuristics

[CGG11] M. Chiarandini, G. Galbiati, S. Gualandi (2011). Efficiency issues in the RLF heuristic for graph coloring. In L. D. Gaspero, A. Schaerf, T. Stützle (eds.), Proceedings of the 9th Metaheuristics International Conference, MIC 2011, pp. 461-469. Dipartimento di Ingegneria Elettrica, Gestionale e Meccanica, Università di Udine, Udine, Italy. ISBN 978-88-90084-3-7. Source code available at http://www.imada.sdu.dk/~marco/gcp/rlf. [ bib | .pdf ]
[CS10] M. Chiarandini, T. Stützle (2010). An Analysis of Heuristics for Vertex Colouring. In P. Festa (ed.), Experimental Algorithms, Proceedings of the 9th International Symposium, (SEA 2010), vol. 6049 of Lecture Notes in Computer Science, pp. 326-337. Springer. Supplementary material and source code available at http://www.imada.sdu.dk/~marco/gcp-study/. [ bib | DOI ]
[Cha04] G. Chaitin (2004). Register allocation and spilling via graph coloring. SIGPLAN Not., vol. 39, no. 4, pp. 66-74. [ bib | DOI ]
[Klo02] W. Klotz (2002). Graph coloring algorithms. Tech. Rep. Mathematik-Bericht 5, Clausthal University of Technology, Clausthal, Germany. [ bib ]
[Pee01] H. A. Peelle (2001). Graph coloring in J: an introduction. In Proceedings of the 2001 International Conference on APL: An Arrays Odyssey, pp. 77-82. Yale University, New Haven, Connecticut, USA. [ bib | DOI ]
[Veg99] S. R. Vegdahl (1999). Using node merging to enhance graph coloring. In PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, pp. 150-154. ACM Press, New York, NY, USA. ISBN 1-58113-094-5. [ bib | DOI ]
[dW90] D. de Werra (1990). Heuristics for Graph Coloring. Computing Supplement, vol. 7, pp. 191-208. [ bib ]
[Lei79] F. T. Leighton (1979). A Graph Coloring Algorithm for Large Scheduling Problems. Journal of Research of the National Bureau of Standards, vol. 84, no. 6, pp. 489-506. [ bib ]
[Woo69] D. C. Wood (1969). A Technique for Coloring a Graph Applicable to Large-Scale Timetabling Problems. Computer Journal, vol. 12, pp. 317-322. [ bib ]



Local Search Methods

[CS10] M. Chiarandini, T. Stützle (2010). An Analysis of Heuristics for Vertex Colouring. In P. Festa (ed.), Experimental Algorithms, Proceedings of the 9th International Symposium, (SEA 2010), vol. 6049 of Lecture Notes in Computer Science, pp. 326-337. Springer. Supplementary material and source code available at http://www.imada.sdu.dk/~marco/gcp-study/. [ bib | DOI ]
[Lew09] R. Lewis (2009). A general-purpose hill-climbing method for order independent minimum gr ouping problems: A case study in graph colouring and bin packing. Computers & Operations Research, vol. 36, no. 7, pp. 2295 - 2310. [ bib | DOI | http ]
[BZ08] I. Blöchliger, N. Zufferey (2008). A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, vol. 35, no. 3, pp. 960-975. [ bib | DOI ]
[BNPP08] T. N. Bui, T. H. Nguyen, C. M. Patel, K.-A. T. Phan (2008). An ant-based algorithm for coloring graphs. Discrete Applied Mathematics, vol. 156, no. 2, pp. 190-200. [ bib | DOI ]
[CD08] M. Caramia, P. Dell'Olmo (2008). Coloring graphs by iterated local search traversing feasible and infeasible solutions. Discrete Applied Mathematics, vol. 156, no. 2, pp. 201-217. [ bib | DOI ]
[CDS08] M. Chiarandini, I. Dumitrescu, T. Stützle (2008). Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems. In C. Blum, M. J. Blesa, A. Roli, M. Sampels (eds.), Hybrid Metaheuristics, vol. 114 of Studies in Computational Intelligence, pp. 117-150. Springer. [ bib | DOI ]
[GHZ08] P. Galinier, A. Hertz, N. Zufferey (2008). An adaptive memory algorithm for the k-coloring problem. Discrete Applied Mathematics, vol. 156, no. 2, pp. 267-279. [ bib | DOI ]
[HPZ08] A. Hertz, M. Plumettaz, N. Zufferey (2008). Variable Space Search for Graph Coloring. Discrete Applied Mathematics, vol. 156, no. 13, pp. 2551 - 2560. [ bib | DOI ]
[MMT08] E. Malaguti, M. Monaci, P. Toth (2008). A Metaheuristic Approach for the Vertex Coloring Problem. INFORMS Journal on Computing, vol. 20, no. 2, pp. p302 - 316. [ bib | DOI | http ]
[TY08] P. M. Talaván, J. Yáñez (2008). The graph coloring problem: A neuronal network approach. European Journal of Operational Research, vol. 191, no. 1, pp. 100 - 111. [ bib | DOI | http ]
[PHK07] D. C. Porumbel, J.-K. Hao, P. Kuntz (2007). A Study of Evaluation Functions for the Graph K-Coloring Problem. In N. Monmarché, E.-G. Talbi, P. Collet, M. Schoenauer, E. Lutton (eds.), Artificial Evolution, vol. 4926 of Lecture Notes in Computer Science, pp. 124-135. Springer. ISBN 978-3-540-79304-5. [ bib | DOI ]
[TY07] M. A. Trick, H. Yildiz (2007). A Large Neighborhood Search Heuristic for Graph Coloring. In P. Van Hentenryck, L. A. Wolsey (eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, vol. 4510 of Lecture Notes in Computer Science, pp. 346-360. Springer. ISBN 978-3-540-72396-7. [ bib | DOI ]
[DT07] K. A. Dowsland, J. M. Thompson (2007). An improved ant colony optimisation heuristic for graph colouring. Discrete Applied Mathematics. In Press, Corrected Proof. [ bib | DOI ]
[GHSL07] B. Gendron, A. Hertz, P. St-Louis (2007). On edge orienting methods for graph coloring. Journal of combinatorial optimization, vol. 13, no. 2, pp. 163-178. [ bib | DOI ]
[OYH07] T. Ono, M. Yagiura, T. Hirata (2007). A vector assignment approach for the graph coloring problem. In Proc. Learning and Intelligent OptimizatioN Conference (LION 2007 II). Trento, Italy. To appear as LNCS. [ bib ]
[CDI06] M. Caramia, P. Dell'Olmo, G. F. Italiano (2006). CHECKCOL: Improved local search for graph coloringstar. Journal of Discrete Algorithms, vol. 4, no. 2, pp. 277-298. [ bib | DOI ]
[GPB05] C. A. Glass, A. Prügel-Bennett (2005). A Polynomially Searchable Exponential Neighbourhood for Graph Colouring. Journal of the Operational Research Society, vol. 56, no. 3, pp. 324-330. [ bib ]
[KGAR05] G. A. Kochenberger, F. Glover, B. Alidaee, C. Rego (2005). An Unconstrained Quadratic Binary Approach to the Vertex Coloring Problem. Annals of Operations Research, vol. 139, no. 1, pp. 229-241. [ bib ]
[DS03] L. Di Gaspero, A. Schaerf (2003). EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software - Practice & Experience, vol. 33, no. 8, pp. 733-765. [ bib ]
[CNP03] V. Cutello, G. Nicosia, M. Pavone (2003). A Hybrid Immune Algorithm with Information Gain for the Graph Coloring Problem. In E. C.-P. et al. (ed.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), vol. 2723 of Lecture Notes in Computer Science, pp. 171-182. Springer Verlag, Berlin, Germany. ISBN 3-540-40602-6. [ bib ]
[AHZ03] C. Avanthay, A. Hertz, N. Zufferey (2003). A variable neighborhood search for graph coloring. European Journal of Operational Research. [ bib ]
[BZ03] I. Blöchliger, N. Zufferey (2003). A Reactive Tabu Search Using Partial Solutions for the Graph Coloring Problem. In D. Kral, J. Sgall (eds.), Coloring graphs from lists with bounded size of their union: result from Dagstuhl Seminar 03391, vol. 156 of ITI-Series. Department of Applied Mathematics and Institute for Theoretical Computer Science, Prague. [ bib ]
[BJH03] A. D. Blas, A. Jagota, R. Hughey (2003). A Range-Compaction Heuristic for Graph Coloring. Journal of Heuristics, vol. 9, no. 3, pp. 489-506. [ bib ]
[CDS03] M. Chiarandini, I. Dumitrescu, T. Stützle (2003). Local Search for the Graph Colouring Problem. A Computational Study. Tech. Rep. AIDA-03-01, Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany. [ bib | .pdf ]
[CS02] M. Chiarandini, T. Stützle (2002). An application of Iterated Local Search to Graph Coloring. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 112-125. Ithaca, New York, USA. [ bib | .pdf ]
[AKL02] M. Allen, G. Kumaran, T. Liu (2002). A Combined Algorithm for Graph-coloring in Register Allocation. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 100-111. Ithaca, New York, USA. [ bib ]
[BP02] T. N. Bui, C. M. Patel (2002). An Ant System Algorithm for Coloring Graphs. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 83-91. Ithaca, New York, USA. [ bib ]
[PS02b] V. Phan, S. Skiena (2002). Coloring Graphs With a General Heuristic Search Engine. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 92-99. Ithaca, New York, USA. [ bib ]
[DBJH02] A. Di Blas, A. Jagota, R. Hughey (2002). Energy function-based approaches to graph coloring. Neural Networks, IEEE Transactions on, vol. 13, no. 1, pp. 81 -91. [ bib | DOI ]
[FH02] A. Fabrikant, T. Hogg (2002). Graph Coloring with Quantum Heuristics. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton, Alberta, Canada. AAAI Press, pp. 22-27. [ bib ]
[GVL02] J. González-Velarde, M. Laguna (2002). Tabu Search with Simple Ejection Chains for Coloring Graphs. Annals of Operations Research, vol. 117, no. 1-4, pp. 165-174. [ bib ]
[PS02a] L. Paquete, T. Stützle (2002). An Experimental Investigation of Iterated Local Search for Coloring Graphs. In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G. Raidl (eds.), Applications of Evolutionary Computing, vol. 2279 of Lecture Notes in Computer Science, pp. 122-131. Springer Verlag, Berlin, Germany. [ bib ]
[Wal01] C. Walshaw (2001). A Multilevel Approach to the Graph Colouring Problem. Tech. Rep. 01/IM/69, School of Computing and Mathematical Science, Univeristy of Greenwich, London, UK. [ bib ]
[HH01b] J.-P. Hamiez, J.-K. Hao (2001). Scatter Search for Graph Coloring. In P. Collet, C. Fonlupt, J.-K. Hao, E. Lutton, M. Schoenauer (eds.), Artificial Evolution, vol. 2310 of Lecture Notes in Computer Science, pp. 168-179. [ bib ]
[HH01a] J.-P. Hamiez, J.-K. Hao (2001). Experimental Investigation of Scatter Search for Graph Coloring. In Proceedings of the Metaheuristics International Conference, pp. 311-316. Porto, Portugal. [ bib ]
[LM01] M. Laguna, R. Martí (2001). A GRASP for Coloring Sparse Graphs. Computational optimization and applications, vol. 19, no. 2, pp. 165-178. [ bib | DOI ]
[FH00] N. Funabiki, T. Higashino (2000). A minimal-state processing search algorithm for graph coloring problems. IEICE Transactions on Fundamentals, vol. E83-A, no. 7, pp. 1420-1430. [ bib ]
[KP98] D. Kirovski, M. Potkonjak (1998). Efficient coloring of a large spectrum of graphs. In DAC '98: Proceedings of the 35th annual conference on Design automation, pp. 427-432. ACM Press, New York, NY, USA. ISBN 0-89791-964-5. [ bib | DOI ]
[Stü98] T. Stützle (1998). Local Search Algorithms for Combinatorial Problems - Analysis, Improvements, and New Applications. Ph.D. thesis, FB Informatik, Technische Universität Darmstadt, Darmstadt, Germany. [ bib ]
[DH97] C. D., A. Hertz (1997). Ants Can Colour Graphs. Journal of the Operational Research Society, vol. 48, pp. 295-305. [ bib ]
[FF96] C. Fleurent, J. Ferland (1996). Object-oriented implementation of heuristics search methods for Graph Coloring, Maximum Clique, and Satisfiability. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 619-652. American Mathematical Society, Providence, RI, USA. [ bib ]
[LC96] G. Lewandowski, A. Condon (1996). Experiments with parallel graph coloring heuristics and applications of graph coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 309-334. American Mathematical Society, Providence, RI, USA. [ bib ]
[Mor96] C. Morgenstern (1996). Distributed Coloration Neighborhood Search. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 335-357. American Mathematical Society, Providence, RI, USA. [ bib ]
[Jag96] A. Jagota (1996). An adaptive, multiple restarts neural network algorithm for graph coloring. European Journal of Operational Research, vol. 93, no. 2, pp. 257-270. [ bib ]
[Cul92] J. Culberson (1992). Iterated Greedy Graph Coloring and the Difficulty Landscape. Tech. Rep. 92-07, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada. [ bib ]
[Her91] A. Hertz (1991). COSINE: A new graph coloring algorithm. Operations Research Letters, vol. 10, no. 7, pp. 411-415. [ bib | DOI ]
[JAMS91] D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon (1991). Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, vol. 39, no. 3, pp. 378-406. [ bib ]
[MS90] C. Morgenstern, H. Shapiro (1990). Coloration neighborhood structures for general graph coloring. In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms, pp. 226-235. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. ISBN 0-89871-251-3. [ bib ]
[Hd87] A. Hertz, D. de Werra (1987). Using Tabu Search Techniques for Graph Coloring. Computing, vol. 39, no. 4, pp. 345-351. [ bib ]



Metaheuristics

[WH12] Q. Wu, J.-K. Hao (2012). Coloring large graphs based on independent set extraction. Computers & Operations Research, vol. 39, no. 2, pp. 283 - 290. [ bib | DOI ]
[GHZ08] P. Galinier, A. Hertz, N. Zufferey (2008). An adaptive memory algorithm for the k-coloring problem. Discrete Applied Mathematics, vol. 156, no. 2, pp. 267-279. [ bib | DOI ]
[DS03] L. Di Gaspero, A. Schaerf (2003). EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software - Practice & Experience, vol. 33, no. 8, pp. 733-765. [ bib ]
[BZ03] I. Blöchliger, N. Zufferey (2003). A Reactive Tabu Search Using Partial Solutions for the Graph Coloring Problem. In D. Kral, J. Sgall (eds.), Coloring graphs from lists with bounded size of their union: result from Dagstuhl Seminar 03391, vol. 156 of ITI-Series. Department of Applied Mathematics and Institute for Theoretical Computer Science, Prague. [ bib ]
[CDS03] M. Chiarandini, I. Dumitrescu, T. Stützle (2003). Local Search for the Graph Colouring Problem. A Computational Study. Tech. Rep. AIDA-03-01, Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany. [ bib | .pdf ]
[CS02] M. Chiarandini, T. Stützle (2002). An application of Iterated Local Search to Graph Coloring. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 112-125. Ithaca, New York, USA. [ bib | .pdf ]
[PS02] L. Paquete, T. Stützle (2002). An Experimental Investigation of Iterated Local Search for Coloring Graphs. In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G. Raidl (eds.), Applications of Evolutionary Computing, vol. 2279 of Lecture Notes in Computer Science, pp. 122-131. Springer Verlag, Berlin, Germany. [ bib ]
[Wal01] C. Walshaw (2001). A Multilevel Approach to the Graph Colouring Problem. Tech. Rep. 01/IM/69, School of Computing and Mathematical Science, Univeristy of Greenwich, London, UK. [ bib ]
[FH00] N. Funabiki, T. Higashino (2000). A minimal-state processing search algorithm for graph coloring problems. IEICE Transactions on Fundamentals, vol. E83-A, no. 7, pp. 1420-1430. [ bib ]
[KP98] D. Kirovski, M. Potkonjak (1998). Efficient coloring of a large spectrum of graphs. In DAC '98: Proceedings of the 35th annual conference on Design automation, pp. 427-432. ACM Press, New York, NY, USA. ISBN 0-89791-964-5. [ bib | DOI ]
[FF96] C. Fleurent, J. Ferland (1996). Object-oriented implementation of heuristics search methods for Graph Coloring, Maximum Clique, and Satisfiability. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 619-652. American Mathematical Society, Providence, RI, USA. [ bib ]
[LC96] G. Lewandowski, A. Condon (1996). Experiments with parallel graph coloring heuristics and applications of graph coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 309-334. American Mathematical Society, Providence, RI, USA. [ bib ]
[Jag96] A. Jagota (1996). An adaptive, multiple restarts neural network algorithm for graph coloring. European Journal of Operational Research, vol. 93, no. 2, pp. 257-270. [ bib ]
[Cul92] J. Culberson (1992). Iterated Greedy Graph Coloring and the Difficulty Landscape. Tech. Rep. 92-07, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada. [ bib ]



Population-based Metaheuristics

[TC11a] O. Titiloye, A. Crispin (2011). Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm. In J. O'Shea, N. Nguyen, K. Crockett, R. Howlett, L. Jain (eds.), Agent and Multi-Agent Systems: Technologies and Applications, vol. 6682 of Lecture Notes in Computer Science, pp. 553-562. Springer Berlin / Heidelberg. ISBN 978-3-642-21999-3. [ bib | DOI ]
[TC11b] O. Titiloye, A. Crispin (2011). Quantum annealing of the graph coloring problem. Discrete Optimization, vol. 8, no. 2, pp. 376 - 384. [ bib | DOI ]
[LH10] Z. Lü, J.-K. Hao (2010). A memetic algorithm for graph coloring. European Journal of Operational Research, vol. 203, no. 1, pp. 241 - 250. [ bib | DOI ]
[PSZ10] M. Plumettaz, D. Schindl, N. Zufferey (2010). Ant Local Search and its efficient adaptation to graph colouring. Journal of Operational Research Society, vol. 61, no. 5, pp. 819 - 826. [ bib | DOI ]
[PHK10] D. C. Porumbel, J.-K. Hao, P. Kuntz (2010). An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research, vol. 37, pp. 1822 - 1832. [ bib | DOI ]
[XL09] X.-F. Xie, J. Liu (2009). Graph coloring by multiagent fusion search. Journal of Combinatorial Optimization, vol. 18, no. 2, pp. 99-123. [ bib | DOI ]
[PHK09] D. Porumbel, J.-K. Hao, P. Kuntz (2009). Diversity Control and Multi-Parent Recombination for Evolutionary Graph Coloring Algorithms. In 9th European Conference on Evolutionary Computation in Combinatorial Optimisation (Evocop 2009). Tübingen, Germany. [ bib | .pdf ]
[BNPP08] T. N. Bui, T. H. Nguyen, C. M. Patel, K.-A. T. Phan (2008). An ant-based algorithm for coloring graphs. Discrete Applied Mathematics, vol. 156, no. 2, pp. 190-200. [ bib | DOI ]
[MMT08] E. Malaguti, M. Monaci, P. Toth (2008). A Metaheuristic Approach for the Vertex Coloring Problem. INFORMS Journal on Computing, vol. 20, no. 2, pp. p302 - 316. [ bib | DOI | http ]
[DT07] K. A. Dowsland, J. M. Thompson (2007). An improved ant colony optimisation heuristic for graph colouring. Discrete Applied Mathematics. In Press, Corrected Proof. [ bib | DOI ]
[TW07] E.-G. Talbi, B. Weinberg (2007). Breaking the search space symmetry in partitioning problems: An application to the graph coloring problem. Theoretical Computer Science, vol. 378, no. 1, pp. 78 - 86. [ bib | DOI ]
[CGG05] C. Croitoru, O. Gheorghies, A. Gheorghies (2005). An Ordering-Based Genetic Approach to Graph Coloring. Tech. Rep. TR 05-03, “Al.I.Cuza” University of Iasi, Faculty of Computer Science. [ bib ]
[GPB03] C. A. Glass, A. Prügel-Bennett (2003). Genetic Algorithms for Graph Colouring: Exploration of Galinier and Hao's Algorithm. Journal of Combinatorial Optimization, vol. 7, no. 3, pp. 229-236. [ bib ]
[BP02] T. N. Bui, C. M. Patel (2002). An Ant System Algorithm for Coloring Graphs. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 83-91. Ithaca, New York, USA. [ bib ]
[CLGA02] C. Croitoru, H. Luchian, O. Gheorghies, A. Apetrei (2002). A New Genetic Graph Coloring Heuristic. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 63-74. Ithaca, New York, USA. [ bib ]
[GHZ02] P. Galinier, A. Hertz, N. Zufferey (2002). Adaptive Memory Algorithms for Graph Colouring. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 75-82. Ithaca, New York, USA. Also available as Technical Report G-2003-35, Les Cachiers du GERAD. [ bib ]
[FLS01] D. Fotakis, S. D. Likothanassis, S. Stefanakos (2001). An Evolutionary Annealing Approach to Graph Coloring. In E. J. W. Boers, J. Gottlieb, P. L. Lanzi, R. E. Smith, S. Cagnoni, E. Hart, G. R. Raidl, H. Tijink (eds.), Applications of Evolutionary Computing, EvoWorkshops 2001, vol. 2037 of Lecture Notes in Computer Science, pp. 120-129. Springer. [ bib ]
[LF01] L. A. N. Lorena, J. C. Furtado (2001). Constructive Genetic Algorithm for Clustering Problems. Evolutionary Computation, vol. 9, no. 3, pp. 309-328. [ bib ]
[MD00] A. Marino, R. I. Damper (2000). Breaking the Symmetry of the Graph Colouring Problem with Genetic Algorithms. In D. Whitley (ed.), Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, pp. 240-245. Las Vegas, Nevada, USA. [ bib ]
[GH99] P. Galinier, J. Hao (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, vol. 3, no. 4, pp. 379-397. [ bib | DOI ]
[DH98] R. Dorne, J. Hao (1998). A New Genetic Local Search Algorithm for Graph Coloring. In A. E. Eiben, T. Bäck, M. Schoenauer, H.-P. Schwefel (eds.), Parallel Problem Solving from Nature - PPSN V, 5th International Conference, vol. 1498 of Lecture Notes in Computer Science, pp. 745-754. Springer Verlag, Berlin, Germany. [ bib ]
[EHH98] A. E. Eiben, J. K. V. D. Hauw, J. I. V. Hemert (1998). Graph Coloring with Adaptive Evolutionary Algorithms. Journal of Heuristics, vol. 4, no. 1, pp. 25-46. [ bib | DOI ]
[DH97] C. D., A. Hertz (1997). Ants Can Colour Graphs. Journal of the Operational Research Society, vol. 48, pp. 295-305. [ bib ]
[Mor96] C. Morgenstern (1996). Distributed Coloration Neighborhood Search. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 335-357. American Mathematical Society, Providence, RI, USA. [ bib ]
[FF96] C. Fleurent, J. Ferland (1996). Genetic and Hybrid Algorithms for Graph Coloring. Annals of Operations Research, vol. 63, pp. 437-464. [ bib ]
[CHD95] D. Costa, A. Hertz, O. Dubuis (1995). Embedding of a Sequential Procedure within an Evolutionary Algorithm for Coloring Problems in Graphs. Journal of Heuristics, vol. 1, no. 1, pp. 105-128. [ bib ]
[Dav91] L. Davis (1991). Order-based Genetic Algorithms and the Graph Coloring Problem. In Handbook of Genetic Algorithms, pp. 72-90. Van Nostrand Reinhold; New York. [ bib ]



Other Hybrid Heuristics

[DR08] I. Dukanovic, F. Rendl (2008). A semidefinite programming-based heuristic for graph coloring. Discrete Applied Mathematics, vol. 156, no. 2, pp. 180-189. [ bib | DOI ]
[Gel08] A. V. Gelder (2008). Another look at graph coloring via propositional satisfiability. Discrete Applied Mathematics, vol. 156, no. 2, pp. 230-243. [ bib | DOI ]
[Pre08] S. D. Prestwich (2008). Generalised graph colouring by a hybrid of local search and constraint programming. Discrete Applied Mathematics, vol. 156, no. 2, pp. 148-158. [ bib | DOI ]
[DR05] I. Dukanovic, F. Rendl (2005). A semidefinite programming based heuristic for graph coloring. Working paper available through the Optimization Online repository. Universitaet Klagenfurt, Institut für Mathematik. [ bib ]
[CD02] M. Caramia, P. Dell'Olmo (2002). Constraint Propagation in Graph Coloring. Journal of Heuristics, vol. 8, no. 1, pp. 83-107. [ bib ]
[CD99] M. Caramia, P. Dell'Olmo (1999). A Fast and Simple Local Search for Graph Coloring. In J. S. Vitter, C. D. Zaroliagis (eds.), Algorithm Engineering, 3rd International Workshop, WAE '99, London, UK, July 19-21, 1999, Proceedings, vol. 1668 of Lecture Notes in Computer Science, pp. 316-329. Springer Verlag, Berlin, Germany. [ bib ]
[GPR96] F. Glover, M. Parker, J. Ryan (1996). Coloring by Tabu Branch and Bound. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 285-307. American Mathematical Society, Providence, RI, USA. [ bib ]
[RA96] C. P. Ravikumar, R. Aggarwal (1996). Parallel search-and-learn techniques and graph coloring. Knowledge-Based Systems, vol. 9, no. 1, pp. 3 - 13. [ bib | DOI | http ]



Theoretical Analysis

[TW07] E.-G. Talbi, B. Weinberg (2007). Breaking the search space symmetry in partitioning problems: An application to the graph coloring problem. Theoretical Computer Science, vol. 378, no. 1, pp. 78 - 86. [ bib | DOI ]
[TH06] Y. Takenaga, K. Higashide (2006). Vertex Coloring of Comparability+e and -e Graphs. In F. V. Fomin (ed.), Graph-Theoretic Concepts in Computer Science, vol. 4271 of Lecture Notes in Computer Science, pp. 102-112. Springer Verlag, Berlin, Germany. [ bib | DOI ]
[CE05] K. Cameron, J. Edmonds (2005). Colouring Some Classes of Perfect Graphs Robustly. Electronic Notes in Discrete Mathematics, vol. 22, pp. 553-556. [ bib | DOI ]
[NW05] J. Nešetřil, G. Woeginger (eds.) (2005). Graph Colorings, Dagstuhl, Germany, 2003, vol. 349. [ bib ]
[Bol04] B. Bollobás (2004). Random graphs. Cambridge studies in advanced mathematics. Cambridge University Press, Cambridge, UK, second edn. [ bib ]
[Chv04] V. Chvátal (2004). Coloring the queen graphs. Web repository (last visited July 2005). [ bib | .html ]
[Gol04] M. C. Golumbic (2004). Algorithmic graph theory and perfect graphs. Elsevier, 2 edn. [ bib ]
[Gon04] G. Gonthier (2004). A computer-checked proof of the four-colour theorem. Available online (Last visited July 2005). [ bib | http ]
[MR02] M. Molloy, B. Reed (2002). Graph colouring and the probabilistic method, vol. 23 of Algorithms and Combinatorics. Springer, Berlin, xiv+326 pp. [ bib ]
[Die00] R. Diestel (2000). Graph Theory. Springer, Berlin, second ed., electronic edn. [ bib ]
[AKS99] N. Alon, M. Krivelevich, B. Sudakov (1999). Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Ser. B, vol. 77, pp. 73-82. [ bib ]
[BLS99] A. Brandstädt, V. B. Le, J. P. Spinrad (1999). Graph Classes: A Survey, vol. 3 of Monographs on Discrete Mathematics and Applications. SIAM Society for Industrial and Applied Mathematics, Philadelphia. [ bib ]
[RSST96] N. Robertson, D. P. Sanders, P. Seymour, R. Thomas (1996). A new proof of the four-colour theorem. Electronic Research Announcements of the American Mathematical Society, vol. 2, no. 1, pp. 17-25. [ bib ]
[JT94] T. R. Jensen, B. Toft (1994). Graph Coloring Problems. John Wiley & Sons, New York, NY, USA. [ bib ]
[Knu94] D. E. Knuth (1994). The Sandwich Theorem. Electron. J. Combin., vol. 1, pp. Article 1, approx. 48 pp. (electronic). [ bib | .pdf ]
[Luc91] T. Luczak (1991). The chromatic number of random graphs. Combinatorica, vol. 11, no. 1, pp. 45-54. [ bib ]
[VL88] R. Venkatesan, L. Levin (1988). Random instances of a graph coloring problem are hard. In STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 217-222. ACM Press, New York, NY, USA. ISBN 0-89791-264-0. [ bib | DOI ]
[BT85] B. Bollobás, A. Thomason (1985). Random graphs of small order. Annals of Discrete Mathematics, vol. 28, pp. 251-256. [ bib ]
[JM82] A. Johri, D. Matula (1982). Probabilistic Bounds and Heuristic Algorihms for Coloring Large Random Graphs. Tech. Rep. 82-CSE-6, Southern Methodist University, Dallas, Texas, USA. [ bib ]
[GLS81] M. Grötschel, L. Lovász, A. Schrijver (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, vol. 1, no. 2, pp. 169-197. [ bib ]
[GJMP80] M. R. Garey, D. S. Johnson, G. L. Miller, C. H. Papadimitriou (1980). The Complexity of Coloring Circular Arcs and Chords. SIAM Journal of Algebraic and Discrete Methods, vol. 1, pp. 216-227. [ bib ]
[GJ79] M. R. Garey, D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, USA. [ bib ]
[Lov79] L. Lovász (1979). On the Shannon capacity of a graph. IEEE Transactions on Information Theory, vol. 25, pp. 1-7. [ bib ]
[AHK77] K. Appel, W. Haken, J. Koch (1977). Every planar map is four colorable. Illinois Journal of Mathematics, vol. 21, pp. 429-567. [ bib ]
[GJ76] M. R. Garey, D. S. Johnson (1976). The Complexity of Near Optimal Graph Coloring. Journal of the Association for Computing Machinery, vol. 23, pp. 43-49. [ bib ]
[Joh74] D. S. Johnson (1974). Worst-case behavior of graph-coloring algorithms. In F. Hoffman, R. Kingsley, R. Levow, R. Mullin, R. Thomas (eds.), South-Eastern Conference on Combinatorics, Graph Theory and Computing, vol. X of Congressus Numerantium, pp. 513-528. Utilitas Mathematica Publishing, Winnipeg, Canada. [ bib ]
[Sto73] L. Stockmeyer (1973). Planar 3-Colorability is NP-Complete. SIGACT News, vol. 5, no. 3, pp. 19-25. [ bib ]
[Kar72] R. M. Karp (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher (eds.), Complexity of Computer Computations, pp. 85-103. Plenum Press, New York, USA. [ bib ]
[Erd61] P. Erdős (1961). Graph theory and probability II. Canadian Journal of Mathematics, vol. 13, pp. 346-352. [ bib ]



Approximation Results

[AN05] D. Achlioptas, A. Naor (2005). The Two Possible Values of the Chromatic Number of a Random Graph. To appear in Annals of Mathematics. [ bib ]
[COT04] A. Coja-Oghlan, A. Taraz (2004). Exact and approximative algorithms for coloring G(n, p). Random structures & algorithms, vol. 24, no. 3, pp. 259-278. [ bib | DOI ]
[CV04] P. Crescenzi, K. Viggo (2004). A compendium of NP optimization problems. Available online (last visited February 2005). [ bib | .html ]
[GRS03] C. Gomes, R. Regis, D. Shmoys (2003). An Improved Approximation for the Partial Latin Square Extension Problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Baltimore, Maryland, USA. [ bib ]
[Pas03] V. T. Paschos (2003). Polynomial approximation and graph-coloring. Computing, vol. 70, no. 1, pp. 41-86. [ bib | DOI ]
[BGS98] M. Bellare, O. Goldreich, M. Sudan (1998). Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM Journal on Computing, vol. 27, no. 3, pp. 804-915. [ bib | DOI ]
[FK98] U. Feige, J. Kilian (1998). Zero Knowledge and the Chromatic Number. Journal of Computer and System Sciences, vol. 57, no. 2, pp. 187-199. [ bib ]
[Hal93] M. M. Halldórsson (1993). A still better performance guarantee for approximate graph coloring. Information Processing Letters, vol. 45, no. 1, pp. 19-23. [ bib | DOI ]
[BR90] B. Berger, J. Rompel (1990). A better performance guarantee for approximate graph colouring. Algorithmica, vol. 5, no. 4, pp. 459-466. [ bib ]
[Wig83] A. Wigderson (1983). Improving the performance guarantee for approximate graph coloring. Journal of the ACM, vol. 30, no. 4, pp. 729-735. [ bib | DOI ]
[Wig82] A. Wigderson (1982). A new approximate graph coloring algorithm. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 325-329. [ bib ]
[Joh74] D. S. Johnson (1974). Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, vol. 9, pp. 256-278. [ bib ]



Lower Bounds

[HCS11] S. Held, W. Cook, E. Sewell (2011). Safe lower bounds for graph coloring. Integer Programming and Combinatoral Optimization, pp. 261-273. [ bib ]
[DR07] I. Dukanovic, F. Rendl (2007). Semidefinite programming relaxations for graph coloring and maximal clique problems. Mathematical Programming, Serie B, vol. 109, no. 2-3, pp. 345-365. [ bib | DOI ]
[GL07b] N. Gvozdenović, M. Laurent (2007). The operator Ψ for the Chromatic Number of a Graph. Optimization Online. [ bib | .html ]
[GL07a] N. Gvozdenović, M. Laurent (2007). Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. Optimization Online. [ bib | .html ]



Empirical Analysis

[LTMG12] R. Lewis, J. Thompson, C. Mumford, J. Gillard (2012). A wide-ranging computational comparison of high-performance graph colouring algorithms. Computers & Operations Research, vol. 39, no. 9, pp. 1933 - 1950. [ bib | DOI | http ]
[PHK10] D. C. Porumbel, J.-K. Hao, P. Kuntz (2010). A search space "cartography" for guiding graph coloring heuristics. Computers & Operations Research, vol. 37, no. 4, pp. 769 - 778. [ bib | DOI ]
[Chi05] M. Chiarandini (2005). Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems. Ph.D. thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany. [ bib | .pdf ]
[GS05] C. Gomes, B. Selman (2005). Can Get Satisfaction. Nature, vol. 435, pp. 751-752. [ bib ]
[BF04] V. C. Barbosa, R. G. Ferreira (2004). On the phase transitions of graph coloring and independent sets. Physica A: Statistical Mechanics and its Applications, vol. 343, no. 1-2. [ bib ]
[HH04] J.-P. Hamiez, J.-K. Hao (2004). An analysis of solution properties of the graph coloring problem. In M. G. C. Resende, J. P. de Sousa, A. Viana (eds.), Metaheuristics: computer decision-making, pp. 325-345. Kluwer Academic Publishers, Norwell, MA, USA. ISBN 1-4020-7653-3. [ bib ]
[Wal02] T. Walsh (2002). 2+p-COL. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 17-22. Ithaca, New York, USA. [ bib ]
[MPWZ02] R. Mulet, A. Pagnani, M. Weigt, R. Zecchina (2002). Coloring random graphs. Physical Review Letters, vol. 89, no. 26. [ bib ]
[CG01] J. Culberson, I. P. Gent (2001). Frozen Development in Graph Coloring. Theoretical Computer Science, vol. 265, no. 1-2. [ bib ]
[Cul01] J. Culberson (2001). Hidden Solutions, Tell-tales, Heuristics and Anti-heuristics. In H. Hoos, T. Stuëtzle (eds.), The IJCAI-01 Workshop on Empirical Methods in Artificial Intelligence, pp. 9-14. [ bib ]
[HH01] J.-P. Hamiez, J.-K. Hao (2001). An analysis of solution properties of the graph coloring problem. In Proceedings of the Metaheuristics International Conference, pp. 193-198. Porto, Portugal. [ bib ]
[Sve01] P. Svenson (2001). From Neel to NPC: Colouring Small Worlds. Computing Research Repository, vol. cs.CC/0107015. [ bib ]
[Wal01] T. Walsh (2001). Search on High Degree Graphs. In B. Nebel (ed.), Proceedings of the 1st International Joint Conference on Artificial Intelligence, pp. 266-274. Morgan Kaufmann, Seattle, Washington, USA. [ bib ]
[CG99] J. Culberson, I. P. Gent (1999). Well out of reach: Why hard problems are hard. Tech. Rep. APES-13-1999, APES (Algorithms, Problems, and Empirical Studies) Group. [ bib ]
[Wal99] T. Walsh (1999). Search in a Small World. In T. Dean (ed.), Proceedings of the 16th International Joint Conference on Artificial Intelligence, pp. 1172-1177. Morgan Kaufmann, Stockholm, Sweden. [ bib ]
[SN98] P. Svenson, M. G. Nordahl (1998). Relaxation in graph coloring and satisfiability problems. Computing Research Repository, vol. cond-mat/9810144. [ bib ]
[Cou97] O. Coudert (1997). Exact coloring of real-life graphs is easy. In DAC '97: Proceedings of the 34th annual conference on Design automation, pp. 121-126. ACM Press, New York, NY, USA, New York, NY, USA. ISBN 0-89791-920-3. [ bib | DOI ]
[CL96] J. Culberson, F. Luo (1996). Exploring the k-colorable Landscape with Iterated Greedy. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 245-284. American Mathematical Society, Providence, RI, USA. [ bib ]
[Hog96] T. Hogg (1996). Refining the Phase Transition in Combinatorial Search. Artificial Intelligence, vol. 81, no. 1-2, pp. 127-154. [ bib ]
[CBP95] J. Culberson, A. Beacham, D. Papp (1995). Hiding our Colors. In Proceedings of the CP'95 Workshop on Studying and Solving Really Hard Problems, pp. 31-42. Cassis, France. [ bib | .html ]
[HJdAa94] A. Hertz, B. Jaumard, M. P. de Aragão (1994). Local optima topology for the k-coloring problem. Discrete Applied Mathematics, vol. 49, no. 1-3, pp. 257-280. [ bib | DOI ]
[Cul92] J. Culberson (1992). Iterated Greedy Graph Coloring and the Difficulty Landscape. Tech. Rep. 92-07, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada. [ bib ]
[CKT91] P. Cheeseman, B. Kanefsky, W. M. Taylor (1991). Where the Really Hard Problems Are. In J. Mylopoulos, R. Reiter (eds.), Proceedings of the 12th International Joint Conference on Artificial Intelligence, pp. 331-337. Morgan Kaufmann Publishers, San Francisco, CA, USA. [ bib ]



Applications

[LT10] R. Lewis, J. Thompson (2010). On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research, vol. In Press, Corrected Proof, pp. -. [ bib | DOI | http ]
[HS08] S. Hossain, T. Steihaug (2008). Graph coloring in the estimation of sparse derivative matrices: Instances and applications. Discrete Applied Mathematics, vol. 156, no. 2, pp. 280-288. [ bib | DOI ]
[ZAG08] N. Zufferey, P. Amstutz, P. Giaccari (2008). Graph Colouring Approaches for a Satellite Range Scheduling Problem. Journal of Scheduling, vol. 11, no. 4, pp. 263 - 277. [ bib ]
[BMPR07] E. K. Burke, J. Mareček, A. J. Parkes, H. Rudová (2007). On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling. Tech. Rep. NOTTCS-TR-2007-10, The University of Nottingham, Nottingham. [ bib | http ]
[GHO07] M. Gamache, A. Hertz, J. O. Ouellet (2007). A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Computers & Operations Research, vol. 34, no. 8, pp. 2384-2395. [ bib | DOI ]
[SRH04] M. D. Smith, N. Ramsey, G. Holloway (2004). A generalized algorithm for graph-coloring register allocation. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pp. 277-288. ACM Press, New York, NY, USA. ISBN 1-58113-807-5. [ bib | DOI ]
[ZKW03] A. Zymolka, A. M. C. A. Koster, R. Wessäly (2003). Transparent optical network design with sparse wavelength conversion. In Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling, pp. 61-80. Budapest, Hungary. [ bib ]
[BB02] N. Barnier, P. Brisset (2002). Graph Coloring for Air Traffic Flow Management. In CPAIOR'02: Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems, pp. 133-147. Le Croisic, France. [ bib ]
[AKL02] M. Allen, G. Kumaran, T. Liu (2002). A Combined Algorithm for Graph-coloring in Register Allocation. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 100-111. Ithaca, New York, USA. [ bib ]
[GS02] C. Gomes, D. Shmoys (2002). Completing Quasigroups or Latin Squares: A Structured Graph Coloring Problem. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 22-39. Ithaca, New York, USA. [ bib ]
[HS02] S. Hossain, T. Steihaug (2002). Graph coloring in the estimation of mathematical derivatives. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 9-16. Ithaca, New York, USA. [ bib ]
[Fre00] R. Freimer (2000). Generalized map coloring for use in geographical information systems. In K.-J. Li, K. Makki, N. Pissinou, S. Ravada (eds.), ACM-GIS 2000, Proceedings of the Eighth ACM Symposium on Advances in Geographic Information Systems, pp. 167-173. ACM press, New York, NY, USA. ISBN 1-58113-319-7. [ bib | DOI ]
[LC96] G. Lewandowski, A. Condon (1996). Experiments with parallel graph coloring heuristics and applications of graph coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 309-334. American Mathematical Society, Providence, RI, USA. [ bib ]
[de 85] D. de Werra (1985). An introduction to timetabling. European Journal of Operational Research, vol. 19, no. 2, pp. 151-162. [ bib | DOI | http ]
[Lei79] F. T. Leighton (1979). A Graph Coloring Algorithm for Large Scheduling Problems. Journal of Research of the National Bureau of Standards, vol. 84, no. 6, pp. 489-506. [ bib ]
[GJS76] M. R. Garey, D. S. Johnson, H. C. So (1976). An Application of Graph Coloring to Printed Circuit Testing. IEEE Transactions on Circuits and Systems, vol. 23, pp. 591-599. [ bib ]
[Woo69] D. C. Wood (1969). A Technique for Coloring a Graph Applicable to Large-Scale Timetabling Problems. Computer Journal, vol. 12, pp. 317-322. [ bib ]



Benchmark Instances

[MN08] K. Mizuno, S. Nishihara (2008). Constructive generation of very hard 3-colorability instances. Discrete Applied Mathematics, vol. 156, no. 2, pp. 218-229. [ bib | DOI ]
[Chv04] V. Chvátal (2004). Coloring the queen graphs. Web repository (last visited July 2005). [ bib | .html ]
[ZKW03] A. Zymolka, A. M. C. A. Koster, R. Wessäly (2003). Transparent optical network design with sparse wavelength conversion. In Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling, pp. 61-80. Budapest, Hungary. [ bib ]
[GS02] C. Gomes, D. Shmoys (2002). Completing Quasigroups or Latin Squares: A Structured Graph Coloring Problem. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 22-39. Ithaca, New York, USA. [ bib ]
[HS02] S. Hossain, T. Steihaug (2002). Graph coloring in the estimation of mathematical derivatives. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 9-16. Ithaca, New York, USA. [ bib ]
[MN02] K. Mizuno, S. Nishihara (2002). Toward Ordered Generation of Exceptionally Hard Instances for Graph 3-Colorability. In D. S. Johnson, A. Mehrotra, M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 1-8. Ithaca, New York, USA. [ bib ]
[CD02b] M. Caramia, P. Dell'Olmo (2002). K-Insertions graphs: a proposal of a new class of benchmarks. Manuscript. [ bib ]
[CD02a] M. Caramia, P. Dell'Olmo (2002). K-FullIns graphs: a proposal of a new class of benchmarks. Manuscript. [ bib ]
[LC96] G. Lewandowski, A. Condon (1996). Experiments with parallel graph coloring heuristics and applications of graph coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 309-334. American Mathematical Society, Providence, RI, USA. [ bib ]
[MT96] A. Mehrotra, M. Trick (1996). A Column Generation Approach for Graph Coloring. INFORMS Journal On Computing, vol. 8, no. 4, pp. 344-354. [ bib ]
[CBP95] J. Culberson, A. Beacham, D. Papp (1995). Hiding our Colors. In Proceedings of the CP'95 Workshop on Studying and Solving Really Hard Problems, pp. 31-42. Cassis, France. [ bib | .html ]
[JAMS91] D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon (1991). Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, vol. 39, no. 3, pp. 378-406. [ bib ]



Monographs and Surveys

[Lew16] R. Lewis (2016). A Guide to Graph Colouring: Algorithms and Applications. Springer, Berlin. ISBN 978-3-319-25728-0. [ bib | DOI ]
[MT09] E. Malaguti, P. Toth (2009). A survey on vertex coloring problems. International Transactions in Operational Research, pp. 1-34. [ bib | DOI ]
[JMT08] D. S. Johnson, A. Mehrotra, M. A. Trick (2008). Special issue on computational methods for graph coloring and its generalizations. Discrete Applied Mathematics, vol. 156, no. 2, pp. 145-146. [ bib | DOI ]
[CDS07] M. Chiarandini, I. Dumitrescu, T. Stützle (2007). Stochastic Local Search Algorithms for the Graph Colouring Problem. In T. F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, Computer & Information Science Series, pp. 63.1-63.17. Chapman & Hall/CRC, Boca Raton, FL, USA. Preliminary version available as Tech. Rep. AIDA-05-03 at Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany. [ bib | .pdf ]
[GH06] P. Galinier, A. Hertz (2006). A survey of local search methods for graph coloring. Computers & Operations Research, vol. 33, pp. 2547-2562. [ bib | DOI ]
[JMT02] D. S. Johnson, A. Mehrotra, M. Trick (eds.) (2002). Proceedings of the Computational Symposium on Graph Coloring and its Generalizations. Ithaca, New York, USA. [ bib ]
[PMX98] P. Pardalos, T. Mavridou, J. Xue (1998). The graph coloring problem: A bibliographic survey, vol. 2, pp. 331-395. Kluwer Academic Publishers, Boston. [ bib ]
[JT96] D. S. Johnson, M. Trick (eds.) (1996). Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Providence, RI, USA. [ bib ]