  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.
