Coloring random graphs

被引：137

作者：

Mulet, R

Pagnani, A

Weigt, M

Zecchina, R

机构：

[1] Abdus Salaam Int Ctr Theoret Phys, I-34100 Trieste, Italy

[2] Univ Havana, Henri Poincare Chair Complex Syst, Havana 10400, Cuba

[3] Univ Havana, Supoerconduct Lab, Fac Phys, IMRE, Havana 10400, Cuba

[4] Univ Roma La Sapienza, Dipartimento Fis, INFM, I-00185 Rome, Italy

[5] Univ Roma La Sapienza, SMC, I-00185 Rome, Italy

[6] Univ Gottingen, Inst Theoret Phys, D-37073 Gottingen, Germany

来源：

PHYSICAL REVIEW LETTERS | 2002年 / 89卷 / 26期

关键词：

D O I：

10.1103/PhysRevLett.89.268701

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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 cis an element of[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.

引用

页数：4