Coloring random graphs

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring, whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.     

Coloring random triangulations

We introduce and solve a two-matrix model for the tri-coloring problem of the vertices of a random triangulation. We present three different solutions: (i) by orthogonal polynomial techniques, (ii) by use of a discrete Hirota bilinear equation, (iii) by direct expansion. The model is found to lie in the universality class of pure two-dimensional quantum gravity, despite the non-polynomiality of its potential.