A New Graph Coloring Algorithm
Abbreviated Journal Title
Computer Science; Hardware & Architecture; Computer Science, Information; Systems; Computer Science, Software Engineering; Computer Scienc; Theory & Methods
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.
Dutton, R. D. and Brigham, R. C., "A New Graph Coloring Algorithm" (1980). Faculty Bibliography 1980s. 60.