Harmonious coloring

From Wikipedia, the free encyclopedia

Harmonious coloring of 7-tree with 3 levels using 12 colors. The harmonius chromatic number of this graph is 12 since the vertices are 57, and the color's pair are ncolor*(ncolor-1)/2 >= 57 iff ncolor>=12. Moreover (3/2)*(7+1)=12(see Mitchem's Formula).
Harmonious coloring of 7-tree with 3 levels using 12 colors. The harmonius chromatic number of this graph is 12 since the vertices are 57, and the color's pair are ncolor*(ncolor-1)/2 >= 57 iff ncolor>=12. Moreover (3/2)*(7+1)=12(see Mitchem's Formula).

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. 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 the path of length 2, which can be 2-colored but has no harmonious coloring with 2 colors.

Some properties of χH(G):

  1. χH(Tk,3) = ⌈(3/2)(k+1)⌉, where Tk,3 is the complete k-ary tree with 3 levels. (Mitchem 1989)

Harmonious coloring was first proposed by Frank, Harary and Plantholt (1982). Still very little is known about it.

See also: Complete coloring

[edit] External links

  • [1] A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards

[edit] 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, 151–157.