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}.$$I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.