This generator will generate n-vertex k-partite graphs in which
Thus, if flatness is 0, the graph is fairly uniform, while as flatness increases the variation in degree may also increase. However, the variation should always be less than that of an equi-partite graph.
The output is written to a file called
flat###_##_#.col where ### = number of vertices, ## = Number of partitions # = flatnessAny pre-existing file of the same name is overwritten.
Here is an example run:
Enter number of vertices 20 density(10ths of percent) 500 number of partitions 3 flatness 0 random seed 39112This produced the output file flat20_3_0.col. The generator produces output in the DIMACS standard format. Descriptions of this and translators to binary formats can be found in Michael Trick's Graph Coloring Instances .
This generator was written after a conversation with Craig Morgenstern at the DIMACS Challenge workshop. Given the results of the coloring of graphs with higher variability in the paper with Feng Luo, and the improvement in hiding cliques using the graphs described in Camouflaging Independent Sets in Quasi-Random Graphs co-authored with Mark Brockington, we thought similar reductions in variance might make the coloring problem more difficult.
This seems to be the case. Although using Iterated Greedy, and other algorithms seems to leave the ridge defined by edge density versus partition number in the same approximate location, the time (i.e. number of iterations) is increased dramatically over equi-partite graphs near the ridge. (See pages 47-50 in TR92-07 Iterated Greedy Graph Coloring and the Difficulty Landscape for a description of the ridge.)
It is suggested that experimenters test their algorithms by varying the edge density, partition number, number of vertices and flatness. This of course means a fairly large number of tests!
I would be interested in hearing of results on these. Also let me know about any useful modifications to the generator or any problems. E-mail to email@example.com.
April 1, 1995