Английская Википедия: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. 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.
Some properties of Шаблон:Math:
- <math>\chi_{H}(T_{k,3}) = \left\lceil\frac{3(k+1)}{2}\right\rceil,</math>
where Шаблон:Math is the complete [[Glossary of graph theory#k-ary|Шаблон:Mvar-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
External links
- A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
References
- Шаблон:Cite journal
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. Шаблон:ISBN.
- Шаблон:Cite journal
