On the Roots of σ-Polynomials

被引：0

作者：

Brown, Jason ^{[1
]}

Erey, Aysel ^{[1
]}

机构：

[1] Dalhousie Univ, Dept Math & Stat, Halifax, NS B3H 3J5, Canada

来源：

JOURNAL OF GRAPH THEORY | 2016年 / 82卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

sigma-polynomial; real roots; chromatic number; chromatic polynomial; compatible polynomials; MINIMUM REAL ROOTS; ADJOINT POLYNOMIALS; CHROMATIC POLYNOMIALS; GRAPHS; COMPLEMENTS;

D O I：

10.1002/jgt.21889

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given a graph G of order n, the sigma-polynomial of G is the generating function sigma(G,x)=Sigma a(i)x(i) where ai 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 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.

引用

页码：90 / 102

页数：13