On Various Algorithms for Estimating the Chromatic Number of a Graph

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.