In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a harmonious coloring is a (proper) vertex coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

 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(T_k,3) = ⌈(3/2)(k+1)⌉, where T_k,3 is the complete k-ary tree
   Glossary of graph theory
   Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
   
   with 3 levels. (Mitchem 1989)

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

External links

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