























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 $-1$ 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 $X_G$. This theorem gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of $X_G$ with respect to elementary symmetric functions.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。