Let P(G, lambda) be the chromatic polynomial of a graph G with n vertices, independence number alpha and clique number w. We show that for every lambda greater than or equal to n, lambda - n + alpha/lambda (lambda - n + alpha - 1/lambda - n + alpha)(alpha) less than or equal toP(G, lambda - 1)/P(G, lambda) less than or equal to lambda - w/lambda (lambda - 1/lambda)(n-w). We characterize the graphs that yield the lower bound or the upper bound. These results give new bounds on the mean colour number mu(G) of G: n - (n - w) (n - 1/n)(n-w) less than or equal tomu(G) less than or equal to n - alpha (alpha - 1/alpha)(alpha).
On the Chromatic Polynomial of a Graph
NOBILI, Paolo
2002-01-01
Abstract
Let P(G, lambda) be the chromatic polynomial of a graph G with n vertices, independence number alpha and clique number w. We show that for every lambda greater than or equal to n, lambda - n + alpha/lambda (lambda - n + alpha - 1/lambda - n + alpha)(alpha) less than or equal toP(G, lambda - 1)/P(G, lambda) less than or equal to lambda - w/lambda (lambda - 1/lambda)(n-w). We characterize the graphs that yield the lower bound or the upper bound. These results give new bounds on the mean colour number mu(G) of G: n - (n - w) (n - 1/n)(n-w) less than or equal tomu(G) less than or equal to n - alpha (alpha - 1/alpha)(alpha).File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
