Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function

Olivier Bernardi (1) , Philippe Nadeau (2, 3, 4)

1 Brandeis University
2 ICJ - Institut Camille Jordan
3 CTN - Combinatoire, théorie des nombres
4 CNRS - Centre National de la Recherche Scientifique

Let G be a graph, and let χG be its chromatic polynomial. For any non-negative integers i, j, we give an interpretation for the evaluation χ (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.

Domaines: Combinatoire [math.CO]

Olivier Bernardi, Philippe Nadeau. Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function. Discrete Mathematics, 2020, 343 (10), ⟨10.1016/j.disc.2020.111989⟩. ⟨hal-02086961⟩