{
  "id": "math/0405339",
  "version": "v2",
  "published": "2004-05-17T22:23:20.000Z",
  "updated": "2005-05-17T00:30:14.000Z",
  "title": "A counterexample to a conjecture of Björner and Lovász on the $χ$-coloring complex",
  "authors": [
    "Shlomo Hoory",
    "Nathan Linial"
  ],
  "comment": "To appear in JCTB",
  "categories": [
    "math.CO"
  ],
  "abstract": "Associated with every graph $G$ of chromatic number $\\chi$ is another graph $G'$. The vertex set of $G'$ consists of all $\\chi$-colorings of $G$, and two $\\chi$-colorings are adjacent when they differ on exactly one vertex. According to a conjecture of Bj\\\"{o}rner and Lov\\'asz, this graph $G'$ must be disconnected. In this note we give a counterexample to this conjecture.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-05-17T00:30:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40",
      "57M15"
    ],
    "keywords": [
      "coloring complex",
      "conjecture",
      "counterexample",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......5339H"
    }
  }
}