Abstract. 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 thresh