(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

**Frozen Development in Graph Coloring**Joseph Culberson and Ian P. Gent APES-19-2000

**On the Complexity of Unfrozen Problems.**Adam Beacham and Joseph Culberson. (Extended abstract) Full proofs for many of the theorems and more detail can be found in Adam Beacham's thesis.

**Empirical Evidence for an Asymptotic Discontinuity in the Backbone of the 3-Coloring Phase Transition**Joseph Culberson and Ian P. Gent APES-16-1999

**Well out of reach: Why hard problems are hard.**Joseph Culberson and Ian P. Gent APES-13-1999

- The ridge identified in TR92-07 and the DIMACS paper can be seen as an example of a similar transition, but for satisfiable instances.

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.

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 *i*th 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.

joe@cs.ualberta.ca

Wed Aug 23 2000