{
  "id": "cond-mat/0403725",
  "version": "v2",
  "published": "2004-03-30T14:47:25.000Z",
  "updated": "2004-07-28T22:32:07.000Z",
  "title": "Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs",
  "authors": [
    "Florent Krzakala",
    "Andrea Pagnani",
    "Martin Weigt"
  ],
  "comment": "23 pages, 10 figures. Replaced with accepted version",
  "journal": "Phys. Rev. E 70, 046705 (2004)",
  "doi": "10.1103/PhysRevE.70.046705",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech",
    "cs.CC"
  ],
  "abstract": "We consider the problem of coloring Erdos-Renyi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-called one-step replica symmetry breaking (1RSB) ansatz. We derive a general criterion for the validity of this ansatz and, applying it to the ground state, we provide evidence that the 1RSB solution gives exact threshold values c_q for the q-COL/UNCOL phase transition. We also study the asymptotic thresholds for q >> 1 finding c_q = 2qlog(q)-log(q)-1+o(1) in perfect agreement with rigorous mathematical bounds, as well as the nature of excited states, and give a global phase diagram of the problem.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2004-07-28T22:32:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stability analysis",
      "high-q asymptotics",
      "coloring problem",
      "global phase diagram",
      "q-col/uncol phase transition"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Phys. Rev. E"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}