On the chromatic polynomial of a graph

On the chromatic polynomial of a graph

0.00 Avg rating0 Votes
Article ID: iaor20031147
Country: Germany
Volume: 92
Issue: 3
Start Page Number: 439
End Page Number: 452
Publication Date: Jan 2002
Journal: Mathematical Programming
Authors: , ,
Abstract:

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ ≥ n, ((λ−n+α)/λ) ((λ−n+α−1)/(λ−n+α))α ≤ (P(G,λ−1)/P(G,λ)) ≤ ((λ−ω)/λ) ((λ−1)/λ)n−ω. We characterize the graphs that yield the lower bound or the upper bound. These results give new bounds on the mean colour number μ(G) of G: n−(n−ω) ((n−1)/n)n−ω ≤ μ(G) ≤ n−α ((α−1)/α)α.

Reviews

Required fields are marked *. Your email address will not be published.