Smallk Coloring Program Manual
J. Culberson

This manual is currently very brief. Smallk is a backtrack based program for coloring graphs which are expected to have a small chromatic number, e.g. from 3 to 8 colors. This link provides a brief overview of the algorithm(postscript). This is also available as an appendix to the paper "Frozen Development in Graph Coloring" to appear in the TCS special issue on phase transitions.

Please read the CONDITIONS OF USE .

To use this program, first create a directory and copy the source code (gzipped tar file) into it. Unpack this, and if you have the make program simply type make to create an executable in the current directory. The source code is in C.

To execute

	smallk filename seed colors [timeout]
Where Smallk outputs statistics and other info to standard output. If it is successful in coloring the graph then it creates a graph filename.res or appends to it if it already exists, and writes out the coloring found. This is a list of colors 1..k for each vertex. The list is preceded by a one line comment.

The program catches SIGINT (cntrl-C on my linux machines) and tries to clean up and print out statistics of the current search. A second interrupt should terminate it immediately.

If you do not want all of the statistics, then simply edit the printstats() routine in stats.c. (As I said this is research code, so you are on your own as to modifications.)

Enjoy!