{
  "id": "math/0410335",
  "version": "v2",
  "published": "2004-10-14T17:18:29.000Z",
  "updated": "2005-01-31T08:33:18.000Z",
  "title": "Higher connectivity of graph coloring complexes",
  "authors": [
    "Sonja Lj. Cukic",
    "Dmitry N. Kozlov"
  ],
  "comment": "16 pages, 6 figures",
  "journal": "IMRN 2005:25 (2005) 1543-1562.",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "The main result of this paper is a proof of the following conjecture of Babson & Kozlov: Theorem. Let G be a graph of maximal valency d, then the complex Hom(G,K_n) is at least (n-d-2)-connected. Here Hom(-,-) denotes the polyhedral complex introduced by Lov\\'asz to study the topological lower bounds for chromatic numbers of graphs. We will also prove, as a corollary to the main theorem, that the complex Hom(C_{2r+1},K_n) is (n-4)-connected, for $n\\geq 3$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-01-31T08:33:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "57M15"
    ],
    "keywords": [
      "graph coloring complexes",
      "higher connectivity",
      "main result",
      "chromatic numbers",
      "topological lower bounds"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math.....10335C"
    }
  }
}