On harmonious colouring of trees (Q426747)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On harmonious colouring of trees |
scientific article |
Statements
On harmonious colouring of trees (English)
0 references
12 June 2012
0 references
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\).
0 references
harmonious chromatic number
0 references