Chromatic Polynomial and Heaps of Pieces

2019/02/06 by Deb, Bishal
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1902.02240

Abstract

Stanley in his paper [Stanley, Richard P.: Acyclic orientations of graphs In: Discrete Mathematics 5 (1973), Nr. 2, S. 171-178.] provided interpretations of the chromatic polynomial when it is substituted with negative integers. Greene and Zaslavsky interpreted the coefficients of the chromatic polynomial in [Greene, Curtis ; Zaslavsky, Thomas: On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. In: Transactions of the American Mathematical Society 280 (1983), jan, Nr. 1, S. 97-97.]. We shall develop an involution on factorisations of heaps of pieces and using this involution, we shall provide bijective proofs to results from both the papers.

Related

• Generalized chromatic polynomials of graphs from Heaps of pieces
• Combinatorial reciprocity for the chromatic polynomial and the chromatic\n symmetric function
• Chromatic polynomials and bialgebras of graphs
• The Amazing Chromatic Polynomial
• A note on a combinatorial interpretation of the e-coefficients of the chromatic symmetric function