CHROMATIC POLYNOMIALS AND SIGMA-POLYNOMIALS

In this paper we present some results on the sequence of coefficients of the chromatic polynomial of a graph relative to the complete graph basis, that is, when it is expressed as the sum of the chromatic polyn omials of complete graphs, These coefficients are the coefficients of what is often called the cr-polynomial. We obtain necessary and suffic ient conditions for this sequence to be symmetrical, and we prove that it is 'skewed' and decreasing beyond its midpoint. We also prove that it is strongly log-concave when G is a complete multipartite graph. ( C) 1996 John Wiley & Sons, Inc.