  We solve the q-state Potts model with anti-ferromagnetic interactions on
large random lattices of finite coordination. Due to the frustration induced by
the large loops and to the local tree-like structure of the lattice this model
behaves as a mean field spin glass. We use the cavity method to compute the
temperature-coordination phase diagram and to determine the location of the
dynamic and static glass transitions, and of the Gardner instability. We show
that for q>=4 the model possesses a phenomenology similar to the one observed
in structural glasses. We also illustrate the links between the positive and
the zero-temperature cavity approaches, and discuss the consequences for the
coloring of random graphs. In particular we argue that in the colorable region
the one-step replica symmetry breaking solution is stable towards more steps of
replica symmetry breaking.

Disordered Systems and Neural Networks;Statistical Mechanics