On harmonious colouring of trees (Q426747)

Summary: Let \(G\) be a simple graph and \(\Delta(G)\) denote the maximum degree of \(G\). A harmonious colouring of \(G\) is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number \(h(G)\) is the least number of colours in such a colouring. In this paper it is shown that if \(T\) is a tree of order \(n\) and \(\Delta(T)\geq\frac{n}{2}\), then there exists a harmonious colouring of \(T\) with \(\Delta(T)+1\) colours such that every colour is used at most twice. Thus \(h(T)=\Delta(T)+1\). Moreover, we prove that if \(T\) is a tree of order \(n\) and \(\Delta(T) \leq \Big\lceil\frac{n}{2}\Big\rceil\), then there exists a harmonious colouring of \(T\) with \(\Big\lceil \frac{n}{2}\Big \rceil +1\) colours such that every colour is used at most twice. Thus \(h(T)\leq \Big\lceil \frac{n}{2} \Big\rceil +1\).