An Integer Programming Model for the Connected Grundy Coloring Problem

A connected vertex ordering of a graph \(G=(V,E)\) is an ordering \(v_1 < v_2 < \ldots < v_n\) of \(V\) such that \(v_i\) has at least one neighbor in \(\{v_1, \ldots, v_{i-1}\}\) for every \(i \in \{2, \ldots, n\}\). A connected Grundy coloring is a greedy coloring applied to a connected vertex ordering. The connected Grundy number of \(G\), denoted by \(\Gamma_c(G)\), is the largest \(k\) such that \(G\) admits a connected \(k\)-Grundy coloring. The parameter \(\Gamma_c(G)\) provides a worst-case bound for the greedy coloring approach applied to a connected vertex ordering. In this work, we revisit the integer programming formulation proposed by \citeonline{Carvalho2023a}, proposing a strengthening of the constraint related to the connectivity of the coloring. Next, we propose two new standard formulations for the connected Grundy number and conduct computational experiments comparing them with the representative formulation presented in \citeonline{Carvalho2023a}.