title: Polynomial iterative algorithms for coloring and analyzing random graphs.
abstract: 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(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] 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 in [c(d),c(q)].
authors.affiliation: International Center for Theoretical Physics, Strada Costiera 11, P.O. Box 586, I-34100 Trieste, Italy.
authors.forename: A
authors.initials: A
authors.lastname: Braunstein
authors.forename: R
authors.initials: R
authors.lastname: Mulet
authors.forename: A
authors.initials: A
authors.lastname: Pagnani
authors.forename: M
authors.initials: M
authors.lastname: Weigt
authors.forename: R
authors.initials: R
authors.lastname: Zecchina