Coloring random graphs
<|reference_start|>Coloring random graphs: We study the graph coloring problem over random graphs of finite average connectivity $c$. Given a number $q$ of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on $q$, we find the precise value of the critical average connectivity $c_q$. Moreover, we show that below $c_q$ there exist a clustering phase $c\in [c_d,c_q]$ in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.<|reference_end|>
@article{mulet2002coloring,
    title={Coloring random graphs},
    author={R. Mulet, A. Pagnani, M. Weigt, R. Zecchina},
    journal={Phys. Rev. Lett. 89, 268701 (2002)},
    year={2002},
    doi={10.1103/PhysRevLett.89.268701},
    archivePrefix={arXiv},
    eprint={cond-mat/0208460},
    primaryClass={cond-mat.stat-mech cond-mat.dis-nn cs.CC}
}