New Bounds for Chromatic Polynomials and Chromatic Roots

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}$forevery$x\in $\mathbb{N}$$. We improve here this bound by showing that $$\pi (G,x)\le (x{)}_{\downarrow k}(x-1{)}^{\mathrm{\Delta }(G)-k+1}{x}^{n-1-\mathrm{\Delta }(G)}$$ for every $x\in \mathbb{N},$ where $\mathrm{\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\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\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.