The complexity of harmonious colouring for trees (Q1346692)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The complexity of harmonious colouring for trees |
scientific article; zbMATH DE number 741471
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The complexity of harmonious colouring for trees |
scientific article; zbMATH DE number 741471 |
Statements
The complexity of harmonious colouring for trees (English)
0 references
10 April 1995
0 references
A harmonious colouring of a simple graph is a proper vertex colouring such that each pair of colours appear together on at most one edge. It is shown in the paper that the problem of determining the least number of colours in a harmonious colouring of a tree is NP-hard.
0 references
complexity
0 references
harmonious colouring
0 references
number of colours
0 references
tree
0 references
