  We consider the problem of coloring the vertices of a large sparse random
graph with a given number of colors so that no adjacent vertices have the same
color. Using the cavity method, we present a detailed and systematic analytical
study of the space of proper colorings (solutions).
  We show that for a fixed number of colors and as the average vertex degree
(number of constraints) increases, the set of solutions undergoes several phase
transitions similar to those observed in the mean field theory of glasses.
First, at the clustering transition, the entropically dominant part of the
phase space decomposes into an exponential number of pure states so that beyond
this transition a uniform sampling of solutions becomes hard. Afterward, the
space of solutions condenses over a finite number of the largest states and
consequently the total entropy of solutions becomes smaller than the annealed
one. Another transition takes place when in all the entropically dominant
states a finite fraction of nodes freezes so that each of these nodes is
allowed a single color in all the solutions inside the state. Eventually, above
the coloring threshold, no more solutions are available. We compute all the
critical connectivities for Erdos-Renyi and regular random graphs and determine
their asymptotic values for large number of colors.
  Finally, we discuss the algorithmic consequences of our findings. We argue
that the onset of computational hardness is not associated with the clustering
transition and we suggest instead that the freezing transition might be the
relevant phenomenon. We also discuss the performance of a simple local Walk-COL
algorithm and of the belief propagation algorithm in the light of our results.
