Graph coloring and monotone functions on posets
type: Item
instance of: scholarly article
title: Graph coloring and monotone functions on posets
zbMATH Open document ID: 0583.05027
DOI: 10.1016/0012-365X(86)90191-3
author: Nathan Linial
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 3933101
zbMATH Keywords: generating function
zbMATH Keywords: graph coloring
zbMATH Keywords: monotone function
zbMATH Keywords: poset acyclic orientation
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: Eulerian numbers
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Ordered structures and partitions
description: scientific article; zbMATH DE number 3933101