Frozen Development: Papers and Data Files

Freezing
(Full resolution images Above(764K) or with Shore Line(764K) )

The following is a series of papers describing experimental and theoretical results on the phase transition and frozenness for graph coloring (and some other problems). The APES reports can be also be retrieved from APES Research Reports

PAPERS:

DATA FILES:

The data files from the experiments described in APES-19-2000 are archived here.

fzdv.tar.gz (gzipped tar file; 37720199 Aug 23 10:05) .

This should unpack as a series of directories labeled 50 through 225, with one hundred files with suffix .fzdv in each directory. The directory number indicates the number of vertices in the graphs in the files contained in it.

FILE FORMAT:

Each file ending with the suffix .fzdv represents one run of the frozen development process. This process generates a permutation of the n choose 2 pairs of vertices. It then builds a sequence of graphs starting with the empty graph and finishing with a 3-partite complete graph, where each graph in the sequence differs from the previous one by the addition of the next edge, except for those edges which are previously frozen with respect to three colorings. See the paper for more details.

The first line of the file consists of 3 numbers; n the number of vertices, n choose 2 the number of pairs, and t the threshold index for this run.

Following this there are n choose 2 lines of four numbers each. These lines should be thought of as a sequence of tuples having implicit labels 1 through n choose 2. The tuple with implicit label i is line i+1 in the file. The first two numbers in line label i are the vertex labels of the ith pair. The next number is a pair type, and is either 1, 2 or 3. The last number in the line is the frozen index, indicating the label of the pair that forced this pair to be the indicated type.

If pair i is of type "1" then it means that it was neither frozen nor freely addable with respect to the graph generated by pairs 1 through i-1. In this case the frozen index of the pair is also i , indicating that only on the addition of the edge was the status of the pair determined.

If a pair i is of type "2" then it means the pair is freely addable. That is, for some earlier graph in the sequence all legal 3-colorings required this pair to have different colors, and this property holds for all following graphs in the sequence. Adding this edge makes no difference to the set of legal colorings. In this case, the frozen index indicates the earliest graph in the sequence for which this property holds; that is, it is the label of the pair that caused pair i to become freely addable.

If a pair i is of type "3" then it is frozen, and cannot be added to the graph without causing it to become uncolorable. In this case, the frozen index indicates the label of the pair that caused it to become frozen.

Note that the threshold t in the first line is the first label to have a pair of type 3 (line t+1 in the file).

Quite a bit of information can be obtained from these files. For example, the set of pairs of type 1 force a uniquely colorable graph (up to relabeling). Scanning for the pair of type 3 with the smallest frozen index yields the first frozen index. Counting all type 3 edges with frozen index less than t yields the number of frozen pairs at the threshold. The same holds for any index i, and from this we get the growth rate in frozen pairs. Merging the type 3 pairs with frozen index at most i gives the collapsed graph at index i.

Taking the graph on the first m pairs yields a random graph from the Gnm distribution. When type 3 pairs are eliminated the graph remains 3-colorable, but the distribution is increasingly skewed from Gnm with increasing m. Thus, when m < t the graph is a random graph.

To determine for example the fraction of random graphs with exactly m edges that are 3-colorable all that is required is to compare m to t in each file. Slightly more effort is sufficient to find the maximum m with 50% colorability.

Back To Coloring Page

Joe Culberson
joe@cs.ualberta.ca
Wed Aug 23 2000