{
  "id": "0812.2937",
  "version": "v1",
  "published": "2008-12-15T22:55:25.000Z",
  "updated": "2008-12-15T22:55:25.000Z",
  "title": "On the chromatic number of random d-regular graphs",
  "authors": [
    "Graeme Kemkes",
    "Xavier Pérez-Giménez",
    "Nicholas Wormald"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k-1)log(k-1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k-1 or k. If moreover d>(2k-3)log(k-1), then the value k-1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of balanced k-colourings, where a colouring is balanced if the number of vertices of each colour is equal.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-12-15T22:55:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "chromatic number",
      "small subgraph conditioning method",
      "smallest integer",
      "proof applies",
      "random d-regular graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0812.2937K"
    }
  }
}