{
  "id": "2505.04366",
  "version": "v1",
  "published": "2025-05-07T12:34:30.000Z",
  "updated": "2025-05-07T12:34:30.000Z",
  "title": "Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs",
  "authors": [
    "Ferenc Bencs",
    "Guus Regts"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "abstract": "We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $\\chi_G(x)$, lie inside the disk centered at $0$ of radius $4.25 \\Delta(G)$, where $\\Delta(G)$ denote the maximum degree of $G$. This improves on a recent result of Jenssen, Patel and the second author, who proved a bound of $5.94\\Delta(G)$. We moreover show that for graphs of sufficiently large girth we can replace $4.25$ by $3.60$ and for claw-free graphs we can replace $4.25$ by $3.81$. Our proofs build on the ideas developed by Jenssen, Patel and the second author, adding some new ideas. A key novel ingredient for claw-free graphs is to use a representation of the coefficients of the chromatic polynomial in terms of the number of certain partial acyclic orientations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-05-07T12:34:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "chromatic polynomial",
      "claw-free graphs",
      "second author",
      "partial acyclic orientations",
      "lie inside"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}