Abstract
We present a reduction from the problem of colouring the vertices of the graph to the maximum independent set problem (MISP) showing that for an n-vertex graph G the sum of the chromatic number of G and the independence number of a graph derived from the complement of G is equal to n. We investigate the applicability of the MISP greedy algorithm to the graph colouring problem. We prove that the well-known Leighton RLF algorithm and an algorithm obtained by modifying the MISP greedy heuristic behave in exactly the same way.
Acknowledgements
The author thanks the anonymous referee for valuable comments and constructive suggestions which allowed him to improve an earlier version of this paper.