Frozen development in graph coloring

We define the 'frozen development' of coloring random graphs. We identify t wo nodes in a graph as frozen if they are of the same color in all legal co lorings and define the collapsed p graph as the one in which all frozen pai rs are merged. This is analogous to studies of the development of a backbon e or spine in SAT (the Satisfiability problem). We first describe in detail the algorithmic techniques used to study frozen development. We present st rong empirical evidence that freezing in 3-coloring is sudden. A single edg e typically causes the size of the graph to collapse in size by 28%. We als o use the frozen development to calculate unbiased estimates of probability of colorability in random graphs. This applies even where this probability is infinitesimal such as 10(-300), although our estimates might be subject to very high variance. We investigate the links between frozen development and the solution cost of graph coloring. In SAT, a discontinuity in the or der parameter has been correlated with the hardness of SAT instances, and o ur data for coloring are suggestive of an asymptotic discontinuity. The unc olorability threshold is known to give rise to hard test instances for grap h-coloring. We present empirical evidence that the cost of coloring thresho ld graphs grows exponentially, when using either a specialist coloring prog ram, or encoding into SAT, or even when using the best of both techniques. Hard instances seem to appear over an increasing range of graph connectivit y as graph size increases. We give theoretical and empirical evidence to sh ow that the size of the smallest uncolorable subgraphs of threshold graphs becomes large as the number of nodes in graphs increases. Finally, we discu ss some of the issues involved in applying our work to the statistical mech anics analysis of coloring. (C) 2001 Elsevier Science BY. All rights reserv ed.