Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
We define the acyclic orientation polynomial of a graph to be the generating function for the sinks of its acyclic orientations. Stanley proved that the number of acyclic orientations is equal to the chromatic polynomial evaluated at up to sign. Motivated by this link between acyclic orientations and the chromatic polynomial, we develop "acyclic orientation" analogues of theorems concerning the chromatic polynomial of Birkhoff, Whitney, and Greene-Zaslavsky. As an application, we provide a new proof for Stanley's sink theorem for chromatic symmetric functions . This theorem gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of with respect to elementary symmetric functions.