DIMACS Graphs and Best Algorithms

Graph	best K / $\chi$	Refferences
dsjc250.5	28/?	[2,6,3,7,12,14,15,18]
dsjc500.1	12/?	[1,2,7,11,12,14,15,18]
dsjc500.5	48/?	[1,6,7,11,14,15,18]
dsjc500.9	126/?	[1,7,11,12,15,18]
dsjc1000.1	20/?	[1,6,7,11,14,15,18]
dsjc1000.5	83/?	[6,11,14]
dsjc1000.9	223/?	[18]
r250.5	65/65	[1,12,14]

Graph	best K / $\chi$	Refferences
r1000.1c	98/?	[1,12,14,18]
r1000.5	234/234	[13,14]
dsjr500.1c	84/84	[17]
dsjr500.5	122/122	[13,14]
le450_15c	15/15	many algorithms
le450_15d	15/15	many algorithms
le450_25c	25/25	[1,12^{p. 353},14,18]
le450.25d	25/25	[1,12^{pp. 353},14,18]

Graph	best K / $\chi$	Refferences
flat300_26_0	26/26	[12,2,4,14]
flat300_28_0	28/28	[1,15]
flat1000_50_0	50/50	[12,1,7,14,15]
flat1000_60_0	60/60	[12,1,7,14,15]
flat1000_76_0	82/76	[14]
latin_square	98/?	[12]
C2000.5	150/?	[12^{p. 352}]
C4000.5	280/?	[4]¹

Graph Descriptions

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

Random graphs generated by Johnson et. al [8] and used extensively afterwords by most graph coloring algorithms: dsjc250.5, dsjc500.5, dsjc500.1, dsjc500.9, dscj1000.1, dsjc1000.5 and dscj1000.9. 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).

Flat graphs due to J. Culberson: flat300_20.0, flat300_26.0, flat300_28.0, flat1000_50.0, flat1000_60.0 and flat1000_76.0. They have been generated by partitioning the vertex set into Kp almost equal sized classes and then by selecting edges only between vertices of different classes. Finding the best legal K-coloring is equivalent to the restoration of the initial partitioning and K=Kp is hence the chromatic number of the graph (denoted by the second number).

Leighton graphs: le450_15a, le450_15b, le450_15c, le450_15d, le450_15a, le450_15b, le450_15c, and le450_25c, they are graphs with the same fixed number of vertices (450) and with known chromatic numbers $\chi_{le}$ (denoted by the end number) [10]; all graphs have a clique of size $\chi_{le}$

The random geometric graphs:

dsjr500.1, dsjr500.5 and dsjr500.c presented by Johnson et. al in [8] along with the 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
r125.1, r125.1c, r125.5, r250.1, r250.5, r1000.1, 1000.1c and r1000.5, 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]
The 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.

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

Class scheduling graphs (school1 and school1.nsh) and latin square graph (latin_square_10) 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 do 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 , in press (doi Available online 8 July 2009).

19. N. Funabiki and T. Higashino, A minimal-state processing search algorithm for graph coloring problems. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 83(7):1420--1430, 2000. [to be added soon]

20. Zhipeng Lü and Jin-Kao Hao, A Memetic Algorithm for Graph Coloring, Accepted and to appear, and to appear in European Journal of Operational Research, 2009., [to be added soon]

Footnotes

...FleurentFerland96(2)¹: The solution is obtained by coloring a smaller residual graph after removing from the initial graph a number of independent sets.

Acknowledgements

This library has been compiled by Daniel Porumbel while working 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 Version 2002-2-1 (1.71) The translation was initiated by Daniel Porumbel on 2008-04-28. The page should be up-to-date, as of July 2009. However, you might also want to check the project Graph Coloring Benchmarks, that is built on wikipedia-styled collaborative work where more people could contribute.

Difficult Graph Coloring Instances:

Graph Descriptions

Bibliography

Footnotes

Acknowledgements