Premium
On the Roots of σ‐Polynomials
Author(s) -
Brown Jason,
Erey Aysel
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21889
Subject(s) - mathematics , combinatorics , chromatic scale , chromatic polynomial , vertex (graph theory) , conjecture , graph , discrete mathematics , order (exchange) , finance , economics
Abstract Given a graph G of order n , the σ‐ polynomial of G is the generating function σ ( G , x ) = ∑ a i x iwhere 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 (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐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.