A large neighborhood search heuristic for graph coloring

We propose a new local search heuristic for graph coloring that searches very large neighborhoods. The heuristic is based on solving a max-cut problem at each step, while the max-cut problem is formally hard, fast heuristics that give "good" cuts are available to solve this. We provide computational results on benchmark instances. The proposed approach is based on similar heuristics used in computer vision.Anglai