The exact value of the harmonious chromatic number of a complete binary tree (Q1366782)

The problem of finding the harmonious chromatic number of a graph \(G\) is known to be NP-hard. The coloring of a graph is harmonious if any pair of colors is used at most once for coloring a pair of adjacent vertices. There is an obvious lower bound for the number \(h(G)\) of colors---the smallest integer \(k\) such that \({k\choose 2}\geq E(G)\). The paper proves that this bound is also the exact value of \(h(G)\) in the class of complete binary trees.