Файл:Harmonious coloring tree.svgHarmonious coloring of the complete 7-ary tree with 3 levels using 12 colors. The harmonious chromatic number of this graph is 12. Any fewer colors will result in a color pair appearing on more than one pair of adjacent vertices. Moreover, by Mitchem's Formula, Шаблон:Math.
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Шаблон:Math of a graphШаблон:Mvar is the minimum number of colors needed for any harmonious coloring of Шаблон:Mvar.
Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus Шаблон:Math. There trivially exist graphs Шаблон:Mvar with Шаблон:Math (where Шаблон:Math is the chromatic number); one example is any path of Шаблон:Nowrap, which can be 2-colored but has no harmonious coloring with 2 colors.