A Computational Framework for the Harmonious Coloring Game: Exact Method and Adversarial Heuristics

The harmonious coloring game (HCG) is an adversarial problem in graphs in which two agents alternate the vertex coloring under distance-2 and uniqueness constraints of the color pairs on the edges. As the variants of the problem are PSPACE-complete, the determination of the harmonious chromatic number of the game represents a computational challenge. In this work, an algorithmic framework for HCG is proposed, which combines an exact method, based on the Minimax algorithm with Alpha-Beta pruning, applied to small instances, and adversarial heuristics for larger scale instances, which includes strategies based on the DSATUR method. Through computational experiments, the influence of topology and adversarial strategy on the number of colors required was indicated: split graphs were among the challenging cases. The heuristics showed a mean absolute deviation of less than one color in relation to the reference values, and the computational time was reduced.