Sample Settings for the Graph Generator

These settings are designed to sample across the "phase transition" for several of the graph classes. See the manual for more explanation of the classes and what they are designed to test. If you find these too difficult (or easy) then try different values for the number of vertices. The samples at fixed k=3 should (mostly) be solveable in "reasonable" time using a conversion to SAT and solvers such as satz-rand. The evacuation graphs with larger k are notable in that non-optimal solutions tend to be farther from the solution in terms of number of colors used than is the case for flat and iid graphs using iterated greedy. Alternatively, we can view this as shifting the boundary of the phase transition. I am curious to see how other solvers do on these.

To see what the input values set run the generator program interactively.

Parameters such as "seed", "k" and "p" should have suitable numerical values substituted as indicated. All inputs below specify no cheat in the output. All output graphs are DIMACS ASCII format. You should do a number of graphs at each setting.

NOTE: The generator guarantees the graph is k-colorable, but does not guarantee the chromatic number. In particular, on the sparser side of the "transition", that is for higher k when p is fixed, or lower values of p for fixed k, the chromatic number is typically less than the hidden coloring.

Equipartite IID graphs

Flat Graphs (flatness 0)

Evacuation Graphs