A SYMMETRICAL FUNCTION GENERALIZATION OF THE CHROMATIC POLYNOMIAL OF A GRAPH

For a finite graph G with d vertices we define a homogeneous symmetric function X(G) of degree d in the variables x(1), x(2), .... If we set x(1) = ... x(n) = 1 and all other x(i) = 0, then we obtain chi(G)(n), the chromatic polynomial of G evaluated at n. We consider the expansion of X(G) in terms of various symmetric function bases. The coefficients in these expansions are related to partitions of the vertices into stable subsets, the Mobius function of the lattice of contractions of G, and the structure of the acyclic orientations of G. The coefficients which arise when X(G) is expanded in terms of elementary symmetric functions are particularly interesting, and for certain graphs are related to the theory of Hecke algebras and Kazhdan-Lusztig polynomials. (C) 1995 Academic Press, Inc.