THE HARMONIOUS CHROMATIC NUMBER OF A COMPLETE BINARY AND TRINARY TREE

The harmonious chromatic number of a graph G, denoted by h(G), is the least number of colors which can be assigned to the vertices of G such that adjacent vertices are colored differently and any two distinct edges have different color pairs. This is a slight variation of a definition given independently by Hopcroft and Krishnamoorthy and by Frank, Harary, and Plantholt. D. Johnson has shown that determining h(G) is an NP-complete problem. In this paper we improve Mitchem's results on the harmonious chromatic number of a complete binary tree and discuss the same problem for a complete trinary tree.