A Hodge decomposition interpretation for the coefficients of the chromatic polynomial

Abstract:

Let $G$ be a simple graph with $n$ nodes. The coloring complex of $G$, as defined by Steingrimsson, has $r$-faces consisting of all ordered set partitions, $(B_1, \ldots ,B_{r+2})$ in which at least one $B_i$ contains an edge of $G$. Jonsson proved that the homology $H_{*}(G)$ of the coloring complex is concentrated in the top degree. In addition, Jonsson showed that the dimension of the top homology is one less than the number of acyclic orientations of $G$.

In this paper, we show that the Eulerian idempotents give a decomposition of the top homology of $G$ into $n-1$ components $H_{n-3}^{(j)}(G)$. We go on to prove that the dimensions of the Hodge pieces of the homology are equal to the absolute values of the coefficients of the chromatic polynomial of $G$. Specifically, if we write $\chi _G(\lambda ) = (\sum _{j=1}^{n-1} c_j (-1)^{n-j} \lambda ^j) + \lambda ^n$, then $dim(H_{n-3}^{(j)}(G)) = c_j$.