Graph colorings and acyclic orientations
Kiem-Phong Vo · Linear and Multilinear Algebra · 1987
This paper presents new combinatorial proofs of two identities due to R. Stanley relating the chromatic polynomial and acyclic orientations of a graph. In addition, using elementary means, explicit formulae for the generating functions of the chromatic numbers and the number of color compatible acyclic orientations are derived. These formulae immediately show a reciprocity law concerning the generating functions.