A. BraunsteinR. MuletA. Pagnani 1 M. WeigtR. Zecchina
A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, R. Zecchina. Polynomial iterative algorithms for coloring and analyzing random graphs. Physical Review E, 2003, 68, ⟨10.1103/PhysRevE.68.036702⟩. ⟨insu-03726414⟩
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 with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity c
- 1. LPTMS – Laboratoire de Physique Théorique et Modèles Statistiques