A CORRELATION-INEQUALITY INVOLVING STABLE SET AND CHROMATIC POLYNOMIALS

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 incarnations. We use the Ahlswede-Daykin Theorem to prove that, for all G, and all positive integers λ, P(G, λ)/λn ≤ A(G, λ-1)λ, where P(G, λ) is the chromatic polynomial of G. © 1993 Academic Press, Inc.