Integer programming formulations for the connected Grundy coloring problem

Given a graph G = (V, E), the connected Grundy coloring problem consists of finding a coloring that can be obtained by a first-fit heuristic through a connected vertex sequence that maximizes the number of colors used. A connected vertex sequence is such that every element in the sequence, except the first, is connected to some element that precedes it. In this article, we propose two integer programming formulations for the connected Grundy coloring problem, a standard formulation and one based on representatives’ idea. Preliminary computational experiments indicate that the representative formulation performs better, especially for graphs with density above of 80%. Together they managed to find the optimal solution for 61.25% of the cases. Furthermore, in the set of instances analyzed, it was seen that the median percentage difference for the solutions to the Grundy coloring problem (in which the connectivity requirements are relaxed) is close to 2.5%.