Harmonious coloring

Summary

In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. It is the opposite of the complete coloring, which instead requires every color pairing to occur at least once. The harmonious chromatic number $\chi_{H}(G)$ of a graph $G$ is the minimum number of colors needed for any harmonious coloring of $G$.