Chromatic polynomials and order ideals of monomials

One expansion of the chromatic polynomial pi(G,x) of a graph G relies on spanning trees of a graph. In fact, for a connected graph G of order n, one can express pi(G,x)=(-1)(n-1)x Sigma(i=1)(n-1) t(i) (1-x)(i), where t(i) is the number of spanning trees with external activity 0 and internal activity i. Moreover, it is known (via commutative ring theory) that t(i) arises as the number of monomials of degree n - i - 1 in a set of monomials closed under division. We describe here how to explicitly carry out this construction algebraically. We also apply this viewpoint to prove a new bound for the roots of chromatic polynomials. (C) 1998 Elsevier Science B.V. All rights reserved.