# 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

• P=1/2 varying number of colors. Generator input:
0 seed 2 500 k 1 0.5 0
Vary k from k=25 to k= 70.
• Colors fixed at 3, varying edge density. Generator input:
0 seed 2 500 3 1 p 0
Vary p from p=0.010 to p=0.020 in steps of 0.001.
Refine by varying p in steps of 0.00025 near the middle of the range. If these are too easy increase n from 500.

#### Flat Graphs (flatness 0)

• P=0.5, colors varying Generator input:
0 seed 6 n k 0.5 0 0
For n=300 vary k from k=16 to k=30 in steps of 2.
For n=1000 vary k from k=40 to k=90 in steps of 5.
• Colors fixed at 3, varying edge density. Generator input:
0 seed 6 500 3 p 0 0
Vary p from p=0.010 to p=0.020 in steps of 0.001.
Refine by varying p in steps of 0.00025 near the middle of the range. If these are too hard, use n=300.

#### Evacuation Graphs

• P=0.5, colors varying Generator input:
0 13765 2 500 k 7 0.5 0 f 1 k 0
Fix f=0.0, vary k (two places!) from k=15 to k=70.
For harder instances, vary f slightly. For example, f=0.001 is enough to generally guarantee that even at k=50 only the hidden coloring will be correct (n=500).
• For colors fixed to 3-colors, varying p.
0 13765 2 700 3 7 p 0 f 1 3 0
Set f to 0.0. Vary p from p=0.009 to p=0.020 in steps of 0.001. Varying f may produce harder instances. n=700 may be too hard at the transition, try n=650