Integer optimization models for dynamic coloring of disturbed graphs

Graph coloring is traditionally treated as a static problem, although many applications involve structures subject to change. This work addresses the problem of dynamic coloring in planar graphs subject to perturbations between successive colorings. The problem is modeled through integer programming formulations that capture different levels of anticipation of perturbations. Three models are proposed: reactive, proactive, and anticipative. While the reactive model adapts the coloring only after a perturbation occurs, the proactive and anticipative models incorporate future structural information into the decision-making process. Experiments conducted on planar graphs in both single- and multi-stage scenarios show that anticipation-based models systematically reduce transition costs and produce more stable colorings.