Genetic Algorithms for Harmonious Graph Coloring

In this work we study the Harmonious Graph Coloring Problem (HGCP), an NP-hard variant of graph coloring with strong combinatorial constraints. We propose and evaluate greedy heuristics, a genetic algorithm, and a hybrid biased random-key genetic algorithm (BRKGA) tailored to explore vertex orderings. Computational experiments on random graphs show that evolutionary approaches significantly outperform greedy methods in sparse and bipartite instances, while remaining competitive in denser settings. The results highlight the potential of hybrid metaheuristics for tackling HGCP and open avenues for topology-aware optimization strategies.