- Source: 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 χ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):
χ
H
(
T
k
,
3
)
=
⌈
3
(
k
+
1
)
2
⌉
,
{\displaystyle \chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil ,}
where Tk,3 is the complete 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
A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
References
Frank, O.; Harary, F.; Plantholt, M. (1982). "The line-distinguishing chromatic number of a graph". Ars Combin. 14: 241–252.
Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
Mitchem, J. (1989). "On the harmonious chromatic number of a graph". Discrete Math. 74 (1–2): 151–157. doi:10.1016/0012-365X(89)90207-0.
Kata Kunci Pencarian:
- Harmonious coloring
- Complete coloring
- Exact coloring
- Graph coloring
- List of graph theory topics
- Graph labeling
- Interval edge coloring
- Incidence coloring
- Symbolist painting
- Light in painting
