Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Florent Krzakala, Andrea Pagnani, Martin Weigt

We consider the problem of coloring Erdos-Renyi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-…