Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
Authors:
- Olivier BernardiOBOlivier Bernardi
- Philippe NadeauPNPhilippe Nadeau
Preprint
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.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- A new two-variable generalization of the chromatic polynomialDiscrete Mathematics & Theoretical Computer Science, 2003
- Orientations Acycliques et le Polynôme ChromatiqueEuropean Journal of Combinatorics, 2001
- Acyclic orientations and chromatic generating functionsDiscrete Mathematics, 2001
- A Symmetric Function Generalization of the Chromatic Polynomial of a GraphAdvances in Mathematics, 1995
- Acyclic orientations of graphsDiscrete Mathematics, 1973