\input zb-basic
\input zb-ioport
\iteman{io-port 01687779}
\itemau{Lass, Bodo}
\itemti{Acyclic orientations and the chromatic polynomial. (Orientations acycliques et le polyn\^ome chromatique.)}
\itemso{Eur. J. Comb. 22, No.8, 1101-1123 (2001).}
\itemab
Summary: The chromatic polynomial $\chi_G(\lambda)$, which is associated with each graph $G$, enumerates its regular colorations with $\lambda$ colors. Stanly showed that $|\chi_G(-1)|$ is equal to the number of acyclic orientations of the graph, a result that was refined by Greene and Zaslavsky. The purpose of the paper is to show that a further refinement can be obtained by interpreting each coefficient of $\chi_G(\lambda)$, when the polynomial is developed with respect to powers of $\lambda$ and $(\lambda- 1)$. A systematic use of the generating functions for set functions enables us to have very short and instructive proofs. Gebhard and Sagan, who had already found combinatorial proofs of two results by Greene and Zaslavsky, suggested that further proofs were to be found. Finally, the set functions algebra allows us to establish a series of new interpretations for Crapo's $\beta_G$ invariant. This paper also brings a new light to the classical results due to Cartier, Foata, Viennot, Brenti, Gessel and Stanly.
\itemrv{~}
\itemcc{}
\itemut{chromatic polynomial; acyclic orientations}
\itemli{doi:10.1006/eujc.2001.0537}
\end