DIMACS Graphs and Best Algorithms

Local search algorithms

Graph	best K / $\chi$	References
dsjc250.5	28/?	[2,3,7,15,18]
dsjc500.1	12/?	[1,2,15,18]
dsjc500.5	48/?	[1,15,18]
dsjc500.9	126/?	[1,15,18]
dsjc1000.1	20/?	[1,14,15,18]
dsjc1000.5	85/?	[18]
dsjc1000.9	223/?	[18]

Graph	best K / $\chi$	References
r250.5	66/65	[1]
r1000.1c	98/?	[1,18]
r1000.5	234/234	[13]
dsjr500.1c	84/84	[17]
dsjr500.5	122/122	[13]
le450_25c	25/25	[1,18]
le450.25d	25/25	[1,18]

Graph	best K / $\chi$	References
flat300_28_0	28/28	[1,15,18]
flat1000_50_0	50/50	[1,15]
flat1000_60_0	60/60	[1,15]
flat1000_76_0	85/76	[18]
latin_square	99/?	[2]
C2000.5	/?	-
C4000.5	/?	-

Hybrid and population-based methods

Graph	best K / $\chi$	References
dsjc250.5	28/?	[6,7,12,14,18,19,20,22]
dsjc500.1	12/?	[7,11,12,14,19,20,22]
dsjc500.5	48/?	[6,7,11,14,19,20,22,23]
dsjc500.9	126/?	[7,11,12,18,19,20,22,23]
dsjc1000.1	20/?	[6,7,11,14,19,20,21,22,23]
dsjc1000.5	83/?	[6,11,14,19,20,21,22,23]
dsjc1000.9	222/?	[21,22,23]

Graph	best K / $\chi$	References
r250.5	65/65	[12,14,19,20,22,23]
r1000.1c	98/?	[12,14 19,20,22 ]
r1000.5	234/234	[14]
dsjr500.1c	85/84	[12,14,19,20,22]
dsjr500.5	122/122	[14,19,20,22,23]
le450_25c	25/25	[12^{p. 353},14,19,20,22,23]
le450.25d	25/25	[12^{pp. 353},14, 19,20,22,23]

Graph	best K / $\chi$	References
flat300_28_0	29/28	[19,20]
flat1000_50_0	50/50	[12,7,14,19,20,21]
flat1000_60_0	60/60	[12,7,14,15,19,20,21]
flat1000_76_0	82/76	[14,19,20,21,22,23]
latin_square	97/?	[23]
C2000.5	146/?	[21 ¹]
C4000.5	260/?	[21 ¹]

Graph Descriptions

All listed graphs are from the Dimacs benchmark [9], and, more exactly, they belong to the following families:

dsjcX.Y Random graphs generated by Johnson et. al [8] and used extensively afterwords by most graph coloring algorithms (like dsjc1000.5). The number of vertices is denoted by the first number while the second digit references the probability that any two vertices establish an edge (the density).

flatX_K Flat graphs due to J. Culberson. They are generated by partitioning the vertex set into K almost equal sized classes and then by selecting edges only between vertices of different classes. Finding the best legal K-coloring is equivalent to restoring this initial partitioning. The second number K is hence the chromatic number (X is the vertex set size).

le450_K Leighton graphs, with the 450 vertices and with known chromatic number K (denoted by the second number) [10]; all graphs have a clique of size K.

dsjrX.Y and rX.Y Random geometric graphs:

dsjrX.Y - graphs presented by Johnson et. al in [8] along with the above dsjc random graphs. They are generated by picking points uniformly at random in a square and by setting an edge between all pairs of vertices situated within a certain distance
rX.Y - graphs generated using the same idea by M. Trick using a program of C. Morgenstern; suffix "c" denotes the complement of a graph. Descriptions can be found in [16]. Chromatic numbers for these graphs are taken from [16,Table 8]. For R1000.5, only the clique number is available, but it is equal to the chromatic number and to the upper bound 234.

C2000.5 and C4000.5 Huge random graphs with up to 4 million edges.

latin_square_10 and school* A latin square graph (and class scheduling graphs respectivelly) generated by Gary Lewandowski in the second Dimacs challenge.

Bibliography

1. I. Blöchliger and N. Zufferey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers and Operations Research, 35(3):960-975, 2008

2. M. Chiarandini and T Stutzle. An application of iterated local search to graph coloring, 2002.

3. I. Devarenne, Mabed H., and A. Caminada. Intelligent neighborhood exploration in local search heuristics. In ICTAI '06: Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence, pages 144-150, Washington, DC, USA, 2006. IEEE Computer Society.

4. C. Fleurent and J.A. Ferland. Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. In D.S. Johnson and M.A. Trick, editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1996, volume 26 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 619--652. American Mathematical Society.

5. D.A. Fotakis, S.D. Likothanassis, and S.K. Stefanakos. An Evolutionary Annealing Approach to Graph Coloring. Applications of Evolutionary Computing. EvoWorkshops2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM. Proceedings, 2037:120-129, 2001.

6. P. Galinier and J.K. Hao. Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization, 3(4):379-397, 1999.

7. P. Galinier, A. Hertz, and N. Zufferey. An Adaptive Memory Algorithm for the K-colouring Problem. Discrete Applied Mathematics, 156(2):267–279, 2008.

8. D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon. Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, 39(3):378-406, 1991.

9. D.S. Johnson and M. Trick. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, 1996.

10. F.T. Leighton. A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, 84(6):489-503, 1979.

11. R. Dorne and J.K. Hao. A new genetic local search algorithm for graph coloring. In A. E. Eiben, T. Back, M. Schoenauer, and H.P. Schwefel, editors, PPSN, volume 1498 of LNCS, pages 745–754, 1998.

12. C. Morgenstern. Distributed coloration neighborhood search. In D.S. Johnson and M.A. Trick, editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 335--358. American Mathematical Society, 1996. ^{Important: Some graphs are found under different names (i.e. G500,0.1 instead of dsjc500.1, see page 348); the table at page 357 does not summarise all the results from the whole paper.}

13. S. Prestwich. Coloration Neighbourhood Search With Forward Checking. Annals of Mathematics and Artificial Intelligence, 34(4):327-340, 2002.

14. E. Malaguti, M. Monaci, and P. Toth. A Metaheuristic Approach for the Vertex Coloring Problem. INFORMS Journal on Computing, 20(2):302, 2008.

15. A. Hertz, M. Plumettaz, and N. Zufferey. Variable Space Search for Graph Coloring. Discrete Applied Mathematics , 156(13): 2551-2560, 2008.

16. E.C. Sewell. An improved algorithm for exact graph coloring. In D.S. Johnson and M.A. Trick, editors, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS series in Discrete Mathematics and Theoretical Computer Science , pages 359--376. American Mathematical Society, 1996.

17. B. Benhamou and M.R. Saidi. Etude de la dominance dans les CSPs a contraintes de difference. Journees Francophones de Programmation par Contraintes, 2006, 63-70 [In French]

18. D. Porumbel, J.K. Hao and P Kuntz. A Search Space "Cartography" for Guiding Graph Coloring Heuristics. Computers & Operations Research , 37(4): 769-778, 2010.

19. Zhipeng Lü and Jin-Kao Hao, A Memetic Algorithm for Graph Coloring, European Journal of Operational Research, 203(1): 241-250, 2010.

20. D. Porumbel, J.K. Hao and P Kuntz. An Evolutionary Approach with Diversity Guarantee and Well-Informed Grouping Recombination for Graph Coloring, Computers & Operations Research, 37(10):1822-1832, 2010.

21. Qinghua Wu, Jin-Kao Hao. Coloring large graphs based on independent set extraction Computers and Operations Research, 39: 283-290, 2012

22. Olawale Titiloye, Alan Crispin. Quantum annealing of the graph coloring problem, Discrete Optimization, 8: 376-384, 2011

23. Olawale Titiloye, Alan Crispin. 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. 2011, Springer Berlin / Heidelberg. ISBN 978-3-642-21999-3.

Footnotes

¹: These large graphs are probably best colored by removing independent sets and applying algorithms on the residual graph (see also 4).

Acknowledgements

This library should be up-to-date, as of August 2011. The first version was created in 2008 by Daniel Porumbel in his PhD project with Jin Kao Hao and Pascale Kuntz. Detailed corrections and verifications were performed by Jean Philippe Hamiez, whose help is acknowledged. Most graph files are obtained from M. Trick's page; however, some files were also obtained via private correspondence. The first html version was produced by LaTeX2HTML translator. However, you might also want to check the project Graph Coloring Benchmarks, that is constructed on wiki collaborative work where anybody could contribute.

Back home

Total visits:

Graph Coloring Instances with Difficult Upper Bounds

Graph Descriptions

Bibliography

Footnotes

Acknowledgements