On the chromatic polynomial of a graph |
| |
| Authors: | David Avis Caterina De Simone Paolo Nobili |
| |
| Institution: | (1) School of Computer Science, McGill University, 3480 University Street, Montreal, Canada, H3A2A7, e-mail: avis@cs.mcgill.ca, CA;(2) Istituto di Analisi dei Sistemi ed Informatica (IASI), CNR, Viale Manzoni 30, 00185 Rome, Italy, e-mail: desimone@iasi.rm.cnr.it, IT;(3) Dipartimento di Matematica, Università di Lecce, Via Arnesano, 73100 Lecce, Italy and IASI-CNR, e-mail: nobili@iasi.rm.cnr.it, IT |
| |
| Abstract: | Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()α≤≤ ()
n
−ω. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour
number μ(G) of G: n− (n−ω)()
n
−ω≤μ(G)≤n−α() α.
Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002 |
| |
| Keywords: | : vertex colorings – chromatic polynomials of graphs |
| 本文献已被 SpringerLink 等数据库收录！ |
|
