A Range-Compaction Heuristic for Graph Coloring

This paper presents a novel heuristic for graph coloring that works on a range of colors and iteratively tries to make this range more compact. This range-compaction heuristic also has a pressure component and an annealing schedule for it. The value of this component is empirically quantified. This algorithm is evaluated on a wide range of DIMACS benchmark graphs, and found to be competitive with state-of-the-art algorithms in terms of solution quality and run time.