On the phase transitions of graph coloring and independent sets
arXiv:cond-mat/0309518 · doi:10.1016/j.physa.2004.05.055
Abstract
We study combinatorial indicators related to the characteristic phase transitions associated with coloring a graph optimally and finding a maximum independent set. 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.
References in corpus (6)
- Optimization with Extremal Dynamics
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Coloring random graphs
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Two novel evolutionary formulations of the graph coloring problem
- The interleaved multichromatic number of a graph