  Based on a non-rigorous formalism called the "cavity method", physicists have
put forward intriguing predictions on phase transitions in discrete structures.
One of the most remarkable ones is that in problems such as random $k$-SAT or
random graph $k$-coloring, very shortly before the threshold for the existence
of solutions there occurs another phase transition called "condensation"
[Krzakala et al., PNAS 2007]. The existence of this phase transition appears to
be intimately related to the difficulty of proving precise results on, e.g.,
the $k$-colorability threshold as well as to the performance of message passing
algorithms. In random graph $k$-coloring, there is a precise conjecture as to
the location of the condensation phase transition in terms of a distributional
fixed point problem. In this paper we prove this conjecture for $k$ exceeding a
certain constant $k_0$.
