๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An inequality for chromatic polynomials

โœ Scribed by D.R. Woodall

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
250 KB
Volume
101
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Woodall, D.R., An inequality for chromatic polynomials, Discrete Mathematics 101 (1992) 327-331. It is proved that if P(G, t) is the chromatic polynomial of a simple graph G with II vertices, m edges, c components and b blocks, and if t S 1, then IP(G, t)/ 2 1t'(tl)hl(l + ys + ys2+ . + yF' +spl), where y = m -n + c, p = n -c -b and s = 1 -t. Equality holds for several classes of graphs with few circuits.

๐Ÿ“œ SIMILAR VOLUMES

A Correlation Inequality Involving Stabl
A Correlation Inequality Involving Stable Set and Chromatic Polynomials
โœ G.E. Farr ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 230 KB

Suppose each vertex of a graph \(G\) is chosen with probability \(p\), these choices being independent. Let \(A(G, p)\) be the probability that no two chosen vertices are adjacent. This is essentially the clique polynomial of the complement of \(G\) which has been extensively studied in a variety of

A Matrix Method for Chromatic Polynomial
A Matrix Method for Chromatic Polynomials
โœ Norman Biggs ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 111 KB

The chromatic polynomials of certain families of graphs can be expressed in terms of the eigenspaces of a linear operator. The operator is represented by a matrix, which is referred to here as the compatibility matrix. In this paper complete sets of eigenfunctions are obtained for several related fa