Coloring random graphs

Details Coloring random graphs Coloring random graphs

2002-08-23

arxiv.org/abs/cond-mat/0208460v2

Phys. Rev. Lett. 89, 268701 (2002)

Physics

Condensed Matter

Statistical Mechanics

4 pages, 1 figure, version to app. in PRL

Scientific paper

10.1103/PhysRevLett.89.268701

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 exist 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.

Affiliated with

Also associated with

No associations

Rating

Coloring random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coloring random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coloring random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-94787