Publication Date:
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}.$$
Iris type:
01.01 Articolo in rivista
Keywords:
Vertex colouring; chromatic polynomial
List of contributors:
DE SIMONE, Caterina
Published in: