Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
<|reference_start|>Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs: We consider the problem of coloring Erdos-Renyi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-called one-step replica symmetry breaking (1RSB) ansatz. We derive a general criterion for the validity of this ansatz and, applying it to the ground state, we provide evidence that the 1RSB solution gives exact threshold values c_q for the q-COL/UNCOL phase transition. We also study the asymptotic thresholds for q >> 1 finding c_q = 2qlog(q)-log(q)-1+o(1) in perfect agreement with rigorous mathematical bounds, as well as the nature of excited states, and give a global phase diagram of the problem.<|reference_end|>
@article{krzakala2004threshold,
    title={Threshold values, stability analysis and high-q asymptotics for the
  coloring problem on random graphs},
    author={Florent Krzakala, Andrea Pagnani and Martin Weigt},
    journal={Phys. Rev. E 70, 046705 (2004)},
    year={2004},
    doi={10.1103/PhysRevE.70.046705},
    archivePrefix={arXiv},
    eprint={cond-mat/0403725},
    primaryClass={cond-mat.dis-nn cond-mat.stat-mech cs.CC}
}