On The Harmonious Colouring of Trees

Abstract

Let \(G\) be a simple graph. A harmonious coloring of \(G\) is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number \(h(G)\) is the least number of colors in such a coloring. In this paper, it is shown that if \(T\) is a tree of order \(n\) and \(\Delta(T) \geq \frac{n}{2}\), then \(h(T) = \Delta(T) + 1\), where \(\Delta(T)\) denotes the maximum degree of \(T\). Let \(T_1\) and \(T_2\) be two trees of order \(n_1\) and \(n_2\), respectively, and \(F = T_1 \cup T_2\). In this paper, it is shown that if \(\Delta(T_i) = \Delta_i\) and \(\Delta_i \geq \frac{n_i}{2}\), for \(i = 1, 2\), then \(h(F) \leq \Delta(F) + 2\). Moreover, if \(\Delta_1 = \Delta_2 = \Delta \geq \frac{n_i}{2}\), for \(i = 1, 2\), then \(h(F) = \Delta + 2\).