Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs

We consider the problem of coloring Erdös-Rényi 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 transition from the colorable to the uncolorable phase with q colors. We also study the asymptotic thresholds for q⪢1 finding c_q=2q ln q−ln 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.