Graph coloring and monotone functions on posets (Q1069950)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Graph coloring and monotone functions on posets
scientific article

    Statements

    Graph coloring and monotone functions on posets (English)
    0 references
    0 references
    1986
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    generating function
    0 references
    graph coloring
    0 references
    monotone function
    0 references
    poset acyclic orientation
    0 references
    chromatic polynomial
    0 references
    Eulerian numbers
    0 references
    0 references