On Harmonious Colouring of Trees

Let G be a simple graph and Delta(G) denote the maximum degree of G. A harmonious colouring of 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. In this paper it is shown that if T is a tree of order n and Delta(T) > n/2, then there exists a harmonious colouring of T with Delta(T) + 1 colours such that every colour is used at most twice. Thus h(T) = Delta(T) + 1. Moreover, we prove that if T is a tree of order n and Delta(T) <= [n/2], then there exists a harmonious colouring of T with [n/2] + 1 colours such that every colour is used at most twice. Thus h(T) <= [n/2] + 1.