Key points are not available for this paper at this time.
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 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 and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.
Building similarity graph...
Analyzing shared references across papers
Loading...
Roberto Mulet
Andrea Pagnani
Martin Weigt
Physical Review Letters
Sapienza University of Rome
University of Göttingen
The Abdus Salam International Centre for Theoretical Physics (ICTP)
Building similarity graph...
Analyzing shared references across papers
Loading...
Mulet et al. (Mon,) studied this question.
www.synapsesocial.com/papers/6a08b9aa280cd4e998e8deec — DOI: https://doi.org/10.1103/physrevlett.89.268701