  We prove that a formula predicted on the basis of non-rigorous physics
arguments [Zdeborova and Krzakala: Phys. Rev. E (2007)] provides a lower bound
on the chromatic number of sparse random graphs. The proof is based on the
interpolation method from mathematical physics. In the case of random regular
graphs the lower bound can be expressed algebraically, while in the case of the
binomial random we obtain a variational formula. As an application we calculate
improved explicit lower bounds on the chromatic number of random graphs for
small (average) degrees. Additionally, show how asymptotic formulas for large
degrees that were previously obtained by lengthy and complicated combinatorial
arguments can be re-derived easily from these new results.
