Harmonious Colorings of Graphs

A harmonious labeling of a graph G of order n and size m is an injective function \(f: V(G) \rightarrow \mathbb {Z}_m\) that induces an injective function \(f': E(G) \rightarrow \mathbb {Z}_m\) defined by \(f'(uv)=f(u)+f(v) \pmod m\) . When G is a tree, then we allow f to repeat one vertex label. A proper vertex coloring \(c: V(G) \rightarrow \mathbb {Z}_k\) is called a harmonious k-coloring if the induced edge coloring \(c': E(G) \rightarrow \mathbb {Z}_k\) defined by \(c'(uv)=c(u)+c(v) \pmod k\) is also proper. The minimum positive integer k for which G has a harmonious k-coloring is called the harmonious chromatic number of G, \(\chi _h(G)\) . The harmonious chromatic number of all trees, cycles, grids, and graphs of diameter at most two are determined, and connections are made to existing graph labelings and colorings.