Graph coloring and monotone functions on posets (Q1069950): Difference between revisions

In this paper it is shown that \[ \sum^{\infty}_{n=1}P_ G(n)x^ n=\frac{Q(x)}{(1-x)^{p+1}}, \] where G is a graph of order p, \(P_ G(x)\) its chromatic polynomial and Q a polynomial with nonnegative coefficients of degree p whose leading coefficient equals the number of acyclic orientations of G, by specializing some fundamental results of \textit{R. P. Stanley} [Ordered structures and partitions, Mem. Amer. Math. Soc. 119 (1972; Zbl 0246.05007)] on monotone functions defined on posets. Note that the coefficients of Q may be regarded as graphical Eulerian numbers, since they coincide to Eulerian numbers whenever G has no edge and preserve many properties of classical Eulerian numbers.