{
  "id": "math/0511343",
  "version": "v5",
  "published": "2005-11-14T12:36:59.000Z",
  "updated": "2008-12-17T22:23:45.000Z",
  "title": "Random regular graphs of non-constant degree: Concentration of the chromatic number",
  "authors": [
    "Sonny Ben-Shimon",
    "Michael Krivelevich"
  ],
  "comment": "18 pages",
  "journal": "Discrete Mathematics, 309(12):4149--4161, 2009",
  "doi": "10.1016/j.disc.2008.12.014",
  "categories": [
    "math.CO",
    "cs.DM",
    "math.PR"
  ],
  "abstract": "In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model $\\Gnd$ for $d=o(n^{1/5})$ is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model $\\Gnp$ with $p=\\frac{d}{n}$. Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for $\\Gnp$ for $p=n^{-\\delta}$ where $\\delta>1/2$. The main tool used to derive such a result is a careful analysis of the distribution of edges in $\\Gnd$, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.",
  "revisions": [
    {
      "version": "v5",
      "updated": "2008-12-17T22:23:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R05",
      "05C80"
    ],
    "keywords": [
      "chromatic number",
      "non-constant degree",
      "binomial random graph model",
      "random regular graph model",
      "two-point concentration result"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....11343B"
    }
  }
}