Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem

The master thesis summarized in this article addresses the Grundy coloring problem and its connected variant. These problems define the worst-case behavior for the well-known and widely used first-fit greedy coloring heuristic (in the second case, with connectivity restrictions). First, we provided a new combinatorial upper bound that can improve over well-established ones from the literature. Moreover, the bound was used to enhance some of the proposed methods. Second, we provided the first optimization approaches to solve the problems for general graphs. We proposed integer programming formulations and biased random-key genetic algorithms (BRKGAs) for the two problem variants. We also filled the gap in the literature by providing the first computational tests for the problems through an extensive benchmark that allowed the evaluation of the proposed approaches and the verification of their practical applicability as a method for evaluating greedy criteria for graph coloring.