The complexity of harmonious colouring for trees (Q1346692): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New upper bounds on harmonious colorings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4740588 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Harmonious Coloring of Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3035312 / rank | |||
Normal rank |
Latest revision as of 12:41, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The complexity of harmonious colouring for trees |
scientific article |
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