Matheuristic Variants of DSATUR for the Vertex Coloring Problem

This paper extends with matheuristic operators the seminal DSATUR heuristic for the Vertex Coloring Problem. Firstly, matheuristics are proposed to initialize saturation computing using a clique, a partial optimal coloring with selected vertices or combining both previous strategies. Secondly, an Integer Linear Programming formulation is designed to have larger local greedy optimization in DSATUR construction scheme. Thirdly, dual bounds are obtained with local optimization to improve first lower bounds implied by cliques. Computational results are provided to analyze inefficiency causes of DSATUR heuristic, highlighting the strengths and weaknesses of DSATUR heuristics.