Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function

Abstract

Let G be a graph, and let $\chi$G be its chromatic polynomial. For any non-negative integers i, j, we give an interpretation for the evaluation $\chi$ (i) G (--j) in terms of acyclic orientations. This recovers the classical interpretations due to Stanley and to Green and Zaslavsky respectively in the cases i = 0 and j = 0. We also give symmetric function refinements of our interpretations, and some extensions. The proofs use heap theory in the spirit of a 1999 paper of Gessel.

minor corrections

References in corpus (1)

• Chromatic Polynomial and Heaps of Pieces

Cited by in corpus (4)

• Power sum expansions for Kromatic symmetric functions using Lyndon heaps
• A power sum expansion for the Kromatic symmetric function
• Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
• Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations