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.
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 is bibliograph is no longer being actively updated on a regular basis.
Also included is the clique hiding generator developed with Mark Brockington.
|
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. 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. |
Laboratory for Algorithmics Research UofA
March 31, 2004.