On Various Algorithms for Estimating the Chromatic Number of a Graph

John Mitchem

The Computer Journal · 1976 · 39 citations · 4 references

DOIFull text

Open access

Concepts

Abstract

The well known problem of colouring the vertices of a graph with the minimum number of colours such that adjacent vertices are coloured differently is used in a variety of scheduling and storage problems. This minimum number of colours is called the chromatic number of the graph G and is denoted by χ(G). A number of algorithms for finding a minimum colouring and thus the chromatic number of a graph are known (Christofides, 1971). However, the computer time required to implement such algorithms is often prohibitive. Thus faster algorithms which do not always yield a minimum colouring are frequently used. In this paper we discuss a number of such algorithms and construct graphs to show that each algorithm can give an arbitrarily bad estimate for the chromatic number of a graph.

References

4