The harmonious coloring number of a graph (Q1182896)

A \(k\)-colouring of a graph \(G\) is a map \(f:V\to C\) such that \(| C|=k\). If \(f(v)=c_ 1\) and \(f(w)=c_ 2\) for adjacent \(v\) and \(w\), we say that the color-pair \(\{c_ 1,c_ 2\}\) is present at the edge \(vw\). As introduced by \textit{J. E. Hopcroft} and \textit{M. S. Krishnamoorthy} [SIAM J. Algebraic Discrete Methods 4, 306-311 (1983; Zbl 0543.05028)] a \(k\)-coloring is harmonious if no color-pair is present at more than one edge, and the harmonious coloring number of \(G\) is the minimum \(k\) such that \(G\) has a harmonious \(k\)-coloring. A \(k\)-coloring is proper if \(f^{-1}(c)\) is independent for every color \(c\in C\). The number \(HC(G)\) is defined in this paper to be the minimum \(k\) such that \(G\) has a proper harmonious \(k\)-coloring. In this paper this number is determined for paths and Cartesian products of paths (2 and 3-dimensional grids) and some bounds that are asymptotically best possible are found for the complete binary trees of height \(k\) and the \(n\)-dimensional cube.