https://hal-insu.archives-ouvertes.fr/insu-03726414Braunstein, A.A.BraunsteinMulet, R.R.MuletPagnani, A.A.PagnaniLPTMS - Laboratoire de Physique Théorique et Modèles Statistiques - UP11 - Université Paris-Sud - Paris 11 - CNRS - Centre National de la Recherche ScientifiqueWeigt, M.M.WeigtZecchina, R.R.ZecchinaPolynomial iterative algorithms for coloring and analyzing random graphsHAL CCSD2003Computational techniquessimulationsComputer science and technologySpin-glass and other random modelsPhase transitions: general studiesCondensed Matter - Disordered Systems and Neural NetworksCondensed Matter - Statistical Mechanics02.70.-c89.20.Ff75.10.Nr05.70.Fh[SDU] Sciences of the Universe [physics]Weigt, Martin2022-07-18 16:36:052023-02-10 04:42:162022-07-18 16:36:07enJournal articleshttps://hal-insu.archives-ouvertes.fr/insu-03726414/document10.1103/PhysRevE.68.036702application/pdf1We 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<SUB>q</SUB>. Moreover, we show that below c<SUB>q</SUB> there exists a clustering phase c∈[c<SUB>d</SUB>,c<SUB>q</SUB>] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c∈[c<SUB>d</SUB>,c<SUB>q</SUB>].