Let $P(G,\lambda)$ be the chromatic polynomial of a graph $G$ with $n$ vertices, independence number $\alpha$ and clique number $\omega$. We show that for every $\lambda\geq n$, $${{\lambda-n+\alpha}\over {\lambda}} \left({{\lambda-n+\alpha-1}\over {\lambda -n+\alpha}}\right)^{\alpha}\leq {{P(G,\lambda -1)}\over {P(G,\lambda)}}\leq {{\lambda-\omega}\over {\lambda}} \left({{\lambda-1}\over {\lambda}}\right)^{n-\omega}.$$ % We characterize the graphs that yield the lower bound or the upper bound. \noindent These results give new bounds on the mean colour number $\mu(G)$ of $G$: $$n - (n-\omega)\left({{n-1}\over {n}}\right)^{n-\omega}\leq \mu(G)\leq n-\alpha\left({{\alpha-1}\over {\alpha}}\right) ^{\alpha}.$$

On the Chromatic Polynomial of a Graph

De Simone C;
2002

Abstract

Let $P(G,\lambda)$ be the chromatic polynomial of a graph $G$ with $n$ vertices, independence number $\alpha$ and clique number $\omega$. We show that for every $\lambda\geq n$, $${{\lambda-n+\alpha}\over {\lambda}} \left({{\lambda-n+\alpha-1}\over {\lambda -n+\alpha}}\right)^{\alpha}\leq {{P(G,\lambda -1)}\over {P(G,\lambda)}}\leq {{\lambda-\omega}\over {\lambda}} \left({{\lambda-1}\over {\lambda}}\right)^{n-\omega}.$$ % We characterize the graphs that yield the lower bound or the upper bound. \noindent These results give new bounds on the mean colour number $\mu(G)$ of $G$: $$n - (n-\omega)\left({{n-1}\over {n}}\right)^{n-\omega}\leq \mu(G)\leq n-\alpha\left({{\alpha-1}\over {\alpha}}\right) ^{\alpha}.$$
2002
Istituto di Analisi dei Sistemi ed Informatica ''Antonio Ruberti'' - IASI
Vertex colouring
chromatic polynomial
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/20.500.14243/454965
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact