Threshold values, stability analysis, and high-qasymptotics 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\left(1\right)$ in perfect agreement with rigorous mathematical bounds, as well as the nature of excited states, and give a global phase diagram of the problem.