The Harmonious Chromatic Number of Deep and Wide Complete n- ary Trees

The harmonious chromatic number of a graph G is the least number of colors which can be used to color V(G) such that adjacent vertices are colored differently and no two edges have the same color pair on their vertices. Unsolved Problem 17.5 of Graph Coloring Problems by Jensen and Toft asks for the harmonious chromatic number of T_m,n the complete n-ary tree on m levels. Let q be the number of edged of T_m,n and k be the smallest positive integer such that the binomial coefficient C(k, 2) ≥ q. We show that for all sufficiently large m, n, the harmonious chromatic number of T_m,n is at most k + 1, and that many such T_m,n have harmonious chromatic number k.