A wide‐ranging computational comparison of high‐performance graph colouring algorithms

This paper reviews the current state of the literature surrounding methods for the general graph colouring problem and presents a broad comparison of six high‐performance algorithms, each belonging to one of the main algorithmic schemes identified. Unlike many previous computational studies in graph colouring, a large range of both artificially generated and real‐world graphs are considered, culminating in over 40,000 individual trials that have consumed more than a decade of computation time in total. The picture painted by the comparison is complex, with each method outperforming all others on at least one occasion; however, general patterns are also observed, particularly with regards to the advantages of hybridising local‐search techniques with global‐based operators.