Title
A New Graph Coloring Algorithm
Abbreviated Journal Title
Comput. J.
Keywords
Computer Science; Hardware & Architecture; Computer Science, Information; Systems; Computer Science, Software Engineering; Computer Scienc; Theory & Methods
Abstract
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.
Journal Title
Computer Journal
Volume
24
Issue/Number
1
Publication Date
1-1-1980
Document Type
Article
Language
English
First Page
85
WOS Identifier
ISSN
0010-4620
Recommended Citation
Dutton, R. D. and Brigham, R. C., "A New Graph Coloring Algorithm" (1980). Faculty Bibliography 1980s. 60.
https://stars.library.ucf.edu/facultybib1980/60
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu