Multipopulation Approaches to the Grundy Staining Problem

The Grundy Coloring Problem stands as a complex challenge in Graph Theory and Combinatorial Optimization. The goal is to determine the maximum number of colors that the first-fit heuristic requires among all possible vertex orderings, ensuring that the coloring is proper. 
This objective fundamentally differs from the Classical Coloring Problem, emphasizing the maximization of color diversity.

In this work, we present two distinct meta-heuristic approaches to solve the problem: Ant Colony Optimization (ACO) and Biased Random-Key Genetic Algorithm (BRKGA), both utilizing multiple populations. The ACO employs semi-independent ant populations and a degree block strategy for vertex selection, while the BRKGA uses multiple populations and a warm start procedure, leveraging useful components for permutation problems. Extensive computational experiments have been conducted to evaluate both algorithms on various graph instances. The results demonstrate each algorithm's capacity to effectively maximize the number of colors used.