Title

A New Graph Coloring Algorithm

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

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

WOS:A1981LF49500016

ISSN

0010-4620

Share

COinS