On the roots of $\sigma$-polynomials

Abstract

Given a graph $G$ of order $n$, the $\sigma$-$polynomial$ of $G$ is the generating function $\sigma (G,x)=\sum a_i{x}^i$ where $a_i$ is the number of partitions of the vertex set of $G$ into $i$ nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti [1] proved that $\sigma$-polynomials of graphs with chromatic number at least $n-2$ had all real roots, and conjectured the same held for chromatic number $n-3$. We affirm this conjecture.

14 pages, 6 figures, 1 table; added keywords, changed one of the author's e-mail address, changed a sentence in the last paragraph of the concluding remarks section