Harmonious coloring
In graph theory, a harmonious coloring is a vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number χH 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 ≤ |V|. There trivially exist graphs G with χH > χ ; 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:
- , where Tk,3 is the complete -ary tree with 3 levels.
Harmonious coloring was first proposed by Harary and Plantholt.
Still very little is known about it.
