Skip to Main Content (Press Enter)

Logo CNR
  • ×
  • Home
  • People
  • Outputs
  • Organizations
  • Expertise & Skills

UNI-FIND
Logo CNR

|

UNI-FIND

cnr.it
  • ×
  • Home
  • People
  • Outputs
  • Organizations
  • Expertise & Skills
  1. Outputs

On the Chromatic Polynomial of a Graph

Academic Article
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
Handle:
https://iris.cnr.it/handle/20.500.14243/454965
Published in:
MATHEMATICAL PROGRAMMING
Journal
  • Use of cookies

Powered by VIVO | Designed by Cineca | 26.5.0.0 | Sorgente dati: PREPROD (Ribaltamento disabilitato)