Abstract
A harmonious colouring of a simple graph 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. It was shown by Hopcroft and Krishnamoorthy (1983) that the problem of determining the harmonious chromatic number of a graph is NP-hard. We show here that the problem remains hard even when restricted to trees.
| Original language | English |
|---|---|
| Pages (from-to) | 133-144 |
| Number of pages | 12 |
| Journal | Discrete Applied Mathematics |
| Volume | 57 |
| Issue number | 2-3 |
| Publication status | Published - 1995 |