Acyclic Orientations of Graphs*
Richard P. Stanley · Birkhäuser Boston eBooks · 2009
Let G be a finite graph with p vertices and x its chromatic polynomial. A combinatorial interpretation is given to the positive integer (-1)p x(-λ), where λ is a positive integer, in terms of acyclic orientations of G. In particular, (-1)p x(-1) is the number of acyclic orientations of G. An application is given to the enumeration of labeled acyclic digraphs. An algebra of full binomial type, in the sense of Doubilet-Rota-Stanley, is constructed which yields the generating functions which occur in the above context.