New Bounds for Chromatic Polynomials and Chromatic Roots

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 \[ π(G,x) \leq (x)_{\downarrow k} (x-1)^{Δ(G)-k+1} x^{n-1-Δ(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\ge 4$ then $\pi (G,x)$ is at most $(x{)}_{\downarrow k}(x-1{)}^{n-k}$ for every real $x\ge n-2+{\left(\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\left(\genfrac{}{}{0ex}{}{k}{2}\right)-n+k\right)}^2$ (it had been previously conjectured that this inequality holds for all $x\ge k$). Finally, we provide an upper bound on the moduli of the chromatic roots that is an improvment over known bounds for dense graphs.

15 pages, 1 figure