Harmony by Order: Constructive He uristics for Harmonious Grap h Coloring with a Color Availability Dictionary

This paper addresses the Harmonious Graph Coloring Problem (HCP), a challenging NP-hard variant of graph coloring where each edge must be associated with a unique pair of vertex colors. We propose two constructive greedy heuristics that build valid harmonious colorings based on vertex orderings and a color availability dictionary. The first heuristic colors each vertex along with its uncolored neighbors, while the second processes one vertex at a time. We evaluate both heuristics on various graph families, including random, bipartite, galaxy, and benchmark graphs, using different vertex ordering strategies. Results highlight the significant impact of vertex ordering on solution quality, especially for sparse graphs, and demonstrate the effectiveness of the proposed methods in generating feasible solutions for complex instances.