On harmonious colouring of trees
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\).
- The complexity of harmonious colouring for trees
- Harmonious coloring: parameterized algorithms and upper bounds
- On the harmonious colouring of trees.
- Harmonious coloring: parameterized algorithms and upper bounds
- Harmonious coloring of trees with large maximum degree
- The Harmonious Chromatic Number of Almost All Trees
- The Harmonious Chromatic Number of Bounded Degree Trees
- The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs
- Harmonious colourings of graphs
- On graceful colorings of trees.
- scientific article; zbMATH DE number 5492384 (Why is no real title available?)
- On harmonious coloring of hypergraphs
- The asymptotic existence of BIBDs having a nesting
- A sharp upper bound for the harmonious total chromatic number of graphs and multigraphs
- Minimally colored trees
This page was built for publication: On harmonious colouring of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426747)
