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).
Titolo: | On the Chromatic Polynomial of a Graph |
Autori: | |
Data di pubblicazione: | 2002 |
Rivista: | |
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). |
Handle: | http://hdl.handle.net/11587/107187 |
Appare nelle tipologie: | Articolo pubblicato su Rivista |