A new graph colouring algorithm

Many heuristics polynomial time algorithms exist to colour the vertices of connected undirected graphs having no loops or multiple edges. Associated with each such algorithm are graphs for which the number of colours required in the colouring produced by the algorithm is significantly greater than the minimum that are necessary. Thus it is desirable to have available a range of such algorithms. One, based on a theorem of Zykov, is described here. It has performed well on most graphs to which it has been applied, including some on which other algorithms fail. However it has its own ‘bad’ graphs, and one such family is listed.