{
  "id": "2410.11028",
  "version": "v1",
  "published": "2024-10-14T19:29:17.000Z",
  "updated": "2024-10-14T19:29:17.000Z",
  "title": "Abelian groups with 3-chromatic Cayley graphs",
  "authors": [
    "Mike Krebs",
    "Maya Sankar"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be an abelian group. The main theorem of this paper asserts that there exists a Cayley graph on $G$ with chromatic number 3 if and only if $G$ is not of exponent 1, 2, or 4. Although motivated by ideas from algebraic topology, our proof may be expressed purely combinatorially. As a by-product, we derive a topological result which is of independent interest. Suppose $X$ is a connected non-bipartite graph, and let $\\mathcal N(X)$ denote its neighborhood complex. We show that if the fundamental group $\\pi_1(\\mathcal N(X))$ or first homology group $H_1(\\mathcal N(X))$ is torsion, then the chromatic number of $X$ is at least 4. This strengthens a classical result of Lov\\'asz, which derives the same conclusion if $\\pi_1(\\mathcal N(X))$ is trivial.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-10-14T19:29:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C25"
    ],
    "keywords": [
      "cayley graph",
      "abelian group",
      "chromatic number",
      "first homology group",
      "paper asserts"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}