THE MEAN CHROMATIC NUMBER OF PATHS AND CYCLES

Authors
ANTHONY M BIGGS N
Citation
M. Anthony et N. Biggs, THE MEAN CHROMATIC NUMBER OF PATHS AND CYCLES, Discrete mathematics, 120(1-3), 1993, pp. 227-231
Citations number
4
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Discrete mathematics → ACNP
ISSN journal
0012365X
Volume
120
Issue
1-3
Year of publication
1993
Pages
227 - 231
Database
ISI
SICI code
0012-365X(1993)120:1-3<227:TMCNOP>2.0.ZU;2-4
Abstract
The mean chromatic number of a graph is defined. This is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. In this note, we ana lyse the asymptotic behaviour of the mean chromatic number for the pat hs and even cycles, using generating function techniques.