{{short description|Vertex coloring where no two linked nodes have the same color pairing}} [[Image:Harmonious coloring tree.svg|right|300px|thumb| Harmonious 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|1=''χ''{{sub|H}}(T{{sub|7,3}}) = ⌈(3/2)(7+1)⌉ = 12}}.]]
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|χ{{sub|H}}(''G'')}} of a graph {{mvar|G}} is the minimum number of colors needed for any harmonious coloring of {{mvar|G}}.
Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus {{math|χ{{sub|H}}(''G'') ≤ {{abs|V(''G'')}}}}. There trivially exist graphs {{mvar|G}} with {{math|χ{{sub|H}}(''G'') > χ(''G'')}} (where {{math|χ}} is the chromatic number); one example is any path of {{nowrap|length > 2}}, which can be 2-colored but has no harmonious coloring with 2 colors.
Some properties of {{math|χ{{sub|H}}(''G'')}}: :<math>\chi_{H}(T_{k,3}) = \left\lceil\frac{3(k+1)}{2}\right\rceil,</math> where {{math|T{{sub|''k'',3}}}} is the complete {{mvar|k}}-ary tree with 3 levels. (Mitchem 1989)
Harmonious coloring was first proposed by Harary and Plantholt (1982). Still very little is known about it.
==See also== * Complete coloring * Harmonious labeling
== External links == *[https://web.archive.org/web/20070820013127/http://www.computing.dundee.ac.uk/staff/kedwards/biblio.html ''A Bibliography of Harmonious Colourings and Achromatic Number''] by Keith Edwards
== References == * {{cite journal | last1 = Frank | first1 = O. | last2 = Harary | first2 = F. | last3 = Plantholt | first3 = M. | year = 1982 | title = The line-distinguishing chromatic number of a graph | journal = Ars Combin | volume = 14 | pages = 241–252 }} * Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. {{ISBN|0-471-02865-7}}. * {{cite journal | doi = 10.1016/0012-365X(89)90207-0 | last1 = Mitchem | first1 = J. | year = 1989 | title = On the harmonious chromatic number of a graph | journal = Discrete Math. | volume = 74 | issue = 1–2 | pages = 151–157 | doi-access = free }}
Category:Graph coloring