Coloring random graphs.

摘要: We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q available colors, we find that with low admit almost always proper coloring, whereas high are uncolorable. Depending on q, precise value critical c . Moreover, show below there exists clustering phase E [c d , ] in which ground states spontaneously divide into an exponential clusters and where proliferation metastable is responsible for onset complexity local search algorithms.