Harmonious coloring

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.

The harmonious chromatic number χH(G) of a graph G is the minimum number of colors needed for any harmonious coloring of G. Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus χH(G) ≤ |V(G)|.

There trivially exist graphs G with χH(G) > χ(G) (where χ is the chromatic number); one example is any path of length > 2, which can be 2-colored but has no harmonious coloring with 2 colors.

Some properties of χH(G): where Tk,3 is the complete k-ary tree with 3 levels.

(Mitchem 1989) Harmonious coloring was first proposed by Harary and Plantholt (1982).