http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7115
On the Chromatic Polynomial of a Graph (Articolo in rivista)
- Type
- Label
- On the Chromatic Polynomial of a Graph (Articolo in rivista) (literal)
- Anno
- 2002-01-01T00:00:00+01:00 (literal)
- Alternative label
Avis, D.; De Simone, C.; Nobili, P. (2002)
On the Chromatic Polynomial of a Graph
in Mathematical programming
(literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Avis, D.; De Simone, C.; Nobili, P. (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto
- We give the best upperbound known in literature on the mean colour number
of a graph which is related to its chromatic polynomial. (literal)
- Note
- ISI Web of Science (WOS) (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
- Avis: School of Computer Sciences, McGill University, Canada
De Simone: Istituto di Analisi dei Sistemi e Informatica, CNR
Nobili: Dipartimento di Matematica, Università di Lecce (literal)
- Titolo
- On the Chromatic Polynomial of a Graph (literal)
- 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}.$$ (literal)
- Prodotto di
- Autore CNR
- Insieme di parole chiave
Incoming links:
- Autore CNR di
- Prodotto
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
- Insieme di parole chiave di
