On the recursive largest first algorithm for graph colouring

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.

Keywords:

• Combinatorial optimization
• Graph colouring
• Heuristics
• Independent set

Acknowledgements

The author thanks the anonymous referee for valuable comments and constructive suggestions which allowed him to improve an earlier version of this paper.

Additional information

Notes on contributors

G. Palubeckis

Email: [email protected]