{
  "id": "1611.09545",
  "version": "v1",
  "published": "2016-11-29T10:05:57.000Z",
  "updated": "2016-11-29T10:05:57.000Z",
  "title": "New Bounds for Chromatic Polynomials and Chromatic Roots",
  "authors": [
    "Jason Brown",
    "Aysel Erey"
  ],
  "comment": "15 pages, 1 figure",
  "journal": "Discrete Mathematics, 338(11) (2015), 1938-1946",
  "categories": [
    "math.CO"
  ],
  "abstract": "If $G$ is a $k$-chromatic graph of order $n$ then it is known that the chromatic polynomial of $G$, $\\pi(G,x)$, is at most $x(x-1)\\cdots (x-(k-1))x^{n-k} = (x)_{\\downarrow k}x^{n-k}$ for every $x\\in \\mathbb{N}$. We improve here this bound by showing that \\[ \\pi(G,x) \\leq (x)_{\\downarrow k} (x-1)^{\\Delta(G)-k+1} x^{n-1-\\Delta(G)}\\] for every $x\\in \\mathbb{N},$ where $\\Delta(G)$ is the maximum degree of $G$. Secondly, we show that if $G$ is a connected $k$-chromatic graph of order $n$ where $k\\geq 4$ then $\\pi(G,x)$ is at most $(x)_{\\downarrow k}(x-1)^{n-k}$ for every real $x\\geq n-2+\\left( {n \\choose 2} -{k \\choose 2}-n+k \\right)^2$ (it had been previously conjectured that this inequality holds for all $x \\geq k$). Finally, we provide an upper bound on the moduli of the chromatic roots that is an improvment over known bounds for dense graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-29T10:05:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "chromatic polynomial",
      "chromatic roots",
      "chromatic graph",
      "dense graphs",
      "upper bound"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}