The complexity of harmonious colouring for trees

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The Harmonious chromatic number h(G) is the least number of colours in such a colouring. It was shown by Hopcroft and Krishnamoorthy that the problem of determining the harmonious chromatic number of a graph is NP-hard. The authors show here that the problem remains hard even when restricted to trees.