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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/107187
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 1
social impact