Graph colorings and related symmetric functions:: ideas and applications -: A description of results, interesting applications, & notable open problems

This paper is a sequel to an earlier paper dealing with a symmetric function generalization X-G of the chromatic polynomial of a finite graph G. We consider the question of when the expansion of X-G in terms of Schur functions has nonnegative coefficients and give a number of applications, including new conditions on the f-vector of a flag complex and a new class of polynomials with real zeros. Some generalizations of X-G are also considered related to the Tutte polynomial, directed graphs, and hypergraphs. (C) 1998 Elsevier Science B.V. All rights reserved.