How Many Colors to Color a Random Graph? Cavity, Complexity, Stability and All That
Florent Krzała · Progress of Theoretical Physics Supplement · 2005
We review recent progress on the statiscal physics study of the problem of coloring random graphs with q colors. We discuss the existence of a threshold at connectivity cq = 2qlog q-log q-1+o(1) separting two phases which are respectivily COL (orable) and UNCOL (orable) with q colors; We also argue that the so-called one-step replica symmetry breaking ansatz used to derive these results give exact threshold values, and draw a general phase diagram of the problem.