{
  "id": "2309.10928",
  "version": "v1",
  "published": "2023-09-19T20:59:55.000Z",
  "updated": "2023-09-19T20:59:55.000Z",
  "title": "Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem",
  "authors": [
    "Matthew Jenssen",
    "Viresh Patel",
    "Guus Regts"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "abstract": "We prove that for any graph $G$ of maximum degree at most $\\Delta$, the zeros of its chromatic polynomial $\\chi_G(x)$ (in $\\mathbb{C}$) lie inside the disc of radius $5.94 \\Delta$ centered at $0$. This improves on the previously best known bound of approximately $6.91\\Delta$. We also obtain improved bounds for graphs of high girth. We prove that for every $g$ there is a constant $K_g$ such that for any graph $G$ of maximum degree at most $\\Delta$ and girth at least $g$, the zeros of its chromatic polynomial $\\chi_G(x)$ lie inside the disc of radius $K_g \\Delta$ centered at $0$, where $K_g$ is the solution to a certain optimization problem. In particular, $K_g < 5$ when $g \\geq 5$ and $K_g < 4$ when $g \\geq 25$ and $K_g$ tends to approximately $3.86$ as $g \\to \\infty$. Key to the proof is a classical theorem of Whitney which allows us to relate the chromatic polynomial of a graph $G$ to the generating function of so-called broken-circuit-free forests in $G$. We also establish a zero-free disc for the generating function of all forests in $G$ (aka the partition function of the arboreal gas) which may be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-19T20:59:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "whitneys broken circuit theorem",
      "chromatic polynomial",
      "lie inside",
      "maximum degree",
      "generating function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}