On the Roots of σ‐Polynomials |
| |
| Authors: | Jason Brown Aysel Erey |
| |
| Affiliation: | DEPARTMENT OF MATHEMATICS AND STATISTICS, DALHOUSIE UNIVERSITY HALIFAX, NOVA SCOTIA, CANADA |
| |
| Abstract: | Given a graph G of order n, the σ‐polynomial of G is the generating function  where  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 (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐polynomials of graphs with chromatic number at least  had all real roots, and conjectured the same held for chromatic number  . We affirm this conjecture. |
| |
| Keywords: | σ ‐polynomial real roots chromatic number chromatic polynomial compatible polynomials |
|
|
