An Iterative Matheuristic Algorithm for the B-Coloring Problem

B-coloring is a problem in graph theory at the basis of several real applications and also used to improve solution methods for the classical coloring problem. Enhanced solutions for the classical coloring problem have in turn impacts on several other practical applications in scheduling, timetabling and telecommunications. Namely, given a graph G = (V, E), the b-coloring problem consists of maximizing the number of colors used while assigning a color to every vertex in V such that no pair of adjacent vertices receive the same color and every color has a representative, called a b-vertex. A vertex can be a b-vertex if it is adjacent to vertices colored with all the colors apart from the one assigned to it. In this paper we present a novel Iterative Matheuristic Algorithm based on considerations about the structure of promising solutions and a mathematical programming model. A vast section of computational experiments shows how the approach is able to find high quality solutions for commonly established datasets from the literature. In particular, the method we propose is able to improve the best known heuristic solution for 38 instances of the 137 considered. The optimality of the bounds previously known for another 5 instances has also been proved by running the approach we propose exhaustively.