Acyclic orientations and chromatic generating functions (Q5937454): Difference between revisions

Let \(P_G(k)\) be the chromatic polynomial of a graph \(G\) with \(n\geq 2\) vertices, none of which is isolated. Let \(R_G(k)= P_G(k)/k(k+1)\). Now fix two adjacent vertices \(a\) and \(z\) in \(G\). Let \({\mathcal O}\) be an acyclic orientation of \(G\) having \(a\) as a source and \(z\) as a sink. A function \(f: V(G)\to \{0,1,\dots, k\}\) is \({\mathcal O}\)-compatible if: (i) if \((i,j)\) is an edge of \({\mathcal O}\), then \(f(i)\leq f(j)\); (ii) \(f(a)= 0\) and \(f(z)= k\); (iii) if \(s\) is another source of \({\mathcal O}\), then \(f(s)> 0\); and (iv) if \(t\) is another sink of \({\mathcal O}\), then \(f(t)< k\). The author shows that the coefficients of the polynomial \[ (1- t)^{n- 1}\sum^\infty_{k= 1} R_G(k) t^k \] are nonnegative and, in turn, that if \(k\) is a nonnegative integer then \((-1)^n R_G(-k)\) is the number of pairs \(({\mathcal O},f)\) such that \({\mathcal O}\) is an acyclic orientation of \(G\) in which \(a\) is a source and \(z\) is a sink, and \(f\) is an \({\mathcal O}\)-compatible function from \(V(G)\) to \(\{0,1,\dots, k\}\).