Prefer a chat interface with context about you and your work?
Threshold values, stability analysis, and high-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>q</mml:mi></mml:math>asymptotics for the coloring problem on random graphs
We consider the problem of coloring Erdös-Rényi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-called one-step replica symmetry breaking (1RSB) ansatz. We derive a general criterion for the validity of this ansatz and, applying it …