On the harmonious chromatic number of a graph (Q1823253)

The harmonious chromatic number h(G) of a graph G is the least number of colours which can be assigned to the vertices of G such that each vertex has exactly one colour, adjacent vertices have different colours, and the endpoints of any two distinct edges determine distinct colour pairs. Determining h(G) is an NP-complete problem. In this paper results on the harmonious chromatic number of trees are presented. The harmonious chromatic number of 2-regular graphs with at most 2 components is given. Further considerations concern the harmonious chromatic number of r- regular graphs with p vertices and of complete n-ary trees on 3 levels.