Upper Bound for the Coefficients of Chromatic polynomials

Abstract

This paper describes an improvement in the upper bound for the magnitude of a coefficient of a term in the chromatic polynomial of a general graph. If $a_r$ is the coefficient of the $q^r$ term in the chromatic polynomial $P(G,q)$, where $q$ is the number of colors, then we find $a_r\le \left(\genfrac{}{}{0ex}{}{e}{v-r}\right)-\left(\genfrac{}{}{0ex}{}{e-g+2}{v-r-g+2}\right)+\left(\genfrac{}{}{0ex}{}{e-k_g-g+2}{v-r-g+2}\right)-{\sum }_{n=1}^{k_g-{\ell }_g}{\sum }_{m=1}^{{\ell }_g-1}\left(\genfrac{}{}{0ex}{}{e-g+1-n-m}{v-r-g}\right)-{\delta }_{g,3}{\sum }_{n=1}^{k_g+{\ell }_{g+1}^{\ast }-{\ell }_g}\left(\genfrac{}{}{0ex}{}{e-{\ell }_g-g+1-n}{v-r-g}\right)$, where $k_g$ is the number of circuits of length $g$ and ${\ell }_g$ and ${\ell }_{g+1}^{\ast }$ are certain numbers defined in the text.

9 pages, Latex