Skip to Main Content (Press Enter)

Logo CNR
  • ×
  • Home
  • Persone
  • Pubblicazioni
  • Strutture
  • Competenze

UNI-FIND
Logo CNR

|

UNI-FIND

cnr.it
  • ×
  • Home
  • Persone
  • Pubblicazioni
  • Strutture
  • Competenze
  1. Pubblicazioni

On the Chromatic Polynomial of a Graph

Articolo
Data di Pubblicazione:
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}.$$
Tipologia CRIS:
01.01 Articolo in rivista
Keywords:
Vertex colouring; chromatic polynomial
Elenco autori:
DE SIMONE, Caterina
Link alla scheda completa:
https://iris.cnr.it/handle/20.500.14243/454965
Pubblicato in:
MATHEMATICAL PROGRAMMING
Journal
  • Utilizzo dei cookie

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