Comparison Between Integer Programming Approaches to the Grundy Staining Problem

Given a graph G = (V, E), a k-coloring is a way of dividing the set of vertices V in k independent sets, denoted by {V1, V2, . . . , Vk}. On a k- coloring, a v vertex ∈ Vi is considered a Grundy vertex if it is adjacent to some vertex w ∈ Vj for all j < i. Grundy's coloring problem seeks find the highest value of k for which there is a k-coloration, where each vertex in coloring be a Grundy vertex. This largest value of k is called a number and is represented by Γ(G). In this work, we investigated and compared three integer programming formulations: two are based on the standard model of partitioning vertices into color classes, while the third is based on the formulation of asymmetric representatives.