On the phase transitions of graph coloring and independent sets

We study combinatorial indicators related to the characteristic phase transitions associated with the optimization problems of coloring the nodes of a graph with the minimum number of colors and of finding an independent set of maximum cardinality in a graph. In particular, we investigate the role of the acyclic orientations of the graph in the hardness of finding the graph's chromatic number and independence number. We provide empirical evidence that, along a sequence of increasingly denser random graphs, the fraction of acyclic orientations that are “shortest” peaks when the chromatic number increases, and that such maxima tend to coincide with locally easiest instances of the problem. Similar evidence is provided concerning the “widest” acyclic orientations and the independence number.