AN INEQUALITY FOR CHROMATIC POLYNOMIALS

被引：6

作者：

WOODALL, DR

机构：

[1] Department of Mathematics, University of Nottingham, Nottingham

来源：

DISCRETE MATHEMATICS | 1992年 / 101卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(92)90613-K

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is proved that if P(G, t) is the chromatic polynomial of a simple graph G with n vertices, m edges, c components and b blocks, and if t less-than-or-equal-to 1, then \P(G, t)\ greater-than-or-equal-to \t(c)(t - 1)b\(1 + gamma-s + gamma-s2 + ... + gamma-s(mu-1) + s(mu), where gamma = m - n + c, mu = n - c - b and s = 1 - t. Equality holds for several classes of graphs with few circuits.

引用

页码：327 / 331

页数：5