Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations

Abstract

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum _{i=1}^n(-1{)}^{n-i}{a}_i{x}^i$, where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $\hat{I}\mu (G)=\sum _{i=1}^n(n-i)a_i/\sum _{i=1}^n{a}_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that $\hat{I}\mu (T_n)<\hat{I}\mu (G)<\hat{I}\mu (K_n)$ holds for any connected graph $G$ of order $n$ which is neither the complete graph $K_n$ nor a tree $T_n$ of order $n$. The most crucial step of our proof is to obtain the interpretation of all $a_i$'s by the number of acyclic orientations of $G$.

20 pages, 23 references. To appear in J. Graph Theory