THE COMPLEXITY OF HARMONIOUS COLORING FOR TREES

A harmonious colouring of a simple graph G is a proper vertex colourin g 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 i n such a colouring. It was shown by Hopcroft and Krishnamoorthy (1983) that the problem of determining the harmonious chromatic number of a graph is NP-hard. We show here that the problem remains hard even when restricted to trees.