A Graph Generator for Various Classes of k-Colorable Graphs

There are now two versions of the generator

  1. A newer version which includes a generator for evacuation graphs. Also some tools, hints at usage etc.
  2. Older Version:
    Source code in C is available via ftp://ftp.cs.ualberta.ca/pub/joe/GraphGenerator/generate.tar.gz. Source Update List

    To use, retrieve the tar file, gunzip it and extract the files using tar -xf tarfile. Then use make to compile it.

Description, Manual, etc.

This program can be used to generate graphs from various classes of k-colorable quasi-random graphs.

A manual 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

       generator filename

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