A Graph Generator for Various Classes of k-Colorable Graphs
There are now two versions of the generator
- A newer version which includes a generator for evacuation graphs. Also
some tools, hints at usage etc.
- Click here for the tar file.
Using tar -xvf should unpack this into a directory called Generator.
See the README
file for additional information, and the manual
- Here are some sample settings
that produce instances varying through the "phase transition" for three
of my favorite classes.
- Here is a sample perl script
to do a range of tests on three coloring, and a
sample calling script
. Subsitute your program at the indicated place in the sample. Note that
this allows you to specify an average degree range (achieved approximately
on average) as input. (This computation of probability to achieve average
degree is correct only for flat, equipartite iid and equipartite evacuation
- The converter to SAT and some other simple tools can be
(tar file should unpack as Tools). Check the README files in each subdirectory.
- For more information on the other classes, e.g. location of hard
and easy regions, see
Hiding Our Colors
Culberson, Beacham and Papp.
- Older Version:
Source code in C
is available via ftp://ftp.cs.ualberta.ca/pub/joe/GraphGenerator/generate.tar.gz.
To use, retrieve the tar file, gunzip it and extract the files using
tar -xf tarfile. Then use make to compile it.
This program can be used to generate graphs from various
classes of k-colorable quasi-random graphs.
describing program use is available. Please read the
conditions of use
Descriptions of some of these classses of graphs can be found in
Exploring the k-colorable Landscape with Iterated Greedy
co-authored with Feng Luo and
Technical Report TR92-07
. The paper
Hiding our colors
with Adam Beacham and Denis Papp describes further results on many of
the newer classes.
To run the program type
The program will prompt for a number of inputs which vary according to
the type of graph desired.
The generator produces output in either the DIMACS standard ASCII format
or DIMACS standard binary format. Descriptions of these and translators
to/from binary formats can be found in Michael Trick's
Graph Coloring Instances
June 4, 2002