# Graph Coloring Page

Joseph Culberson.

This page is an on-going project to provide graph coloring resources. Please email joe@cs.ualberta.ca with suggestions for additional links and information.

## Graph Coloring Bibliography

Herein is a bibliography of papers, reports etc. in bibtex format which are related to graph coloring and clique finding. The main emphasis is on vertex coloring, and in particular on algorithms for obtaining vertex colorings.

I wish to thank all those who sent me notices and information used in the bibliography. Special acknowledgement to Loretta Bogert-O'Brien who spent many hours chasing down and entering obscure references.

This bibliography is no longer being updated. Search is no longer supported.

## Graph Coloring Programs

These links lead to source code for coloring graphs.

## Graph Generator Programs

My intention is to provide several graph generators that will support empirical research into the characteristics of various coloring algorithms. Thus, I want generators that will exhibit variations of various characteristics of graphs, such as degree (expectation and variation), hidden colorings, girth, edge distributions etc.

Also included is the clique hiding generator developed with Mark Brockington.

## Links to Other Sites

Here are a few links to other sites with graph coloring resources.
• COLOR02/03/04: Graph Coloring and its Generalizations
• Network Resources for Coloring a Graph by Michael Trick (trick@cmu.edu). This includes an on-line survey of graph coloring and a set of Graph Coloring Instances in DIMACS standard format.  WARNING!!! If you wish to test your code on DIMACS flat graphs, be certain to obtain the examples at the DIMACS site. Due to an error on my part, these examples were first posted without having a final step that permutes the vertex order. As a result those versions can be solved by a simple inorder greedy approach and may possibly be solved by any algorithm that traverses the vertices in order, which can be very misleading. (Ironically, I had commented out the code for permuting the vertices in order to test for errors). Despite my efforts and nearly a decade later, I still periodically receive solution claims based on copies of the erroneous instances. A BETTER APPROACH Obtain the graph generator and run a series of tests through the "phase transition". For example, for p=1/2 and n=1000 you should vary k from 40 to 95 in steps of 5, doing a number of tests at each k. After initial results, you may wish to refine the experiment in the most difficult regions. To date, to my knowledge, no one has solved these graphs consistently throughout this range (with flatness=0). DIMACS binary format and MSVC I have received a couple of error reports about some of the DIMACS files not unpacking properly, in particular the Brockington clique files. Donovan Hare reports that ''Turns out in MSVC the fopen command requires the "rb" option not just the "r" option.''   I cannot verify this since I do not run MS, but worth considering if you have difficulties.
• The Second DIMACS Challenge
• Graph Coloring Problems -- The archive. Here are the archives for the book "Graph Coloring Problems" by Tommy R. Jensen and Bjarne Toft (Wiley Interscience 1995). I recommend this book.
• Culberson Papers and reports by J. Culberson on graph coloring and related problems.

August 27, 2010.