The mean chromatic number of paths and cycles |
| |
Authors: | Martin Anthony Norman Biggs |
| |
Institution: | Department of Statistical and Mathematical Sciences, The London School of Economics, London WC2A 2AE, UK |
| |
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 analyse the asymptotic behaviour of the mean chromatic number for the paths and even cycles, using generating function techniques. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |