Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
- 주제(키워드) 도움말 Acyclic orientations , The generating function for sinks , Deletion-contraction recursion , The sink theorem , Chromatic symmetric functions
- 발행기관 ACADEMIC PRESS INC ELSEVIER SCIENCE
- 발행년도 2021
- 총서유형 Journal
- 본문언어 영어
초록/요약 도움말
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. (C) 2021 Elsevier Inc. All rights reserved.
more