The complexity of harmonious colouring for trees

K. Edwards, C. McDiarmid

    Research output: Contribution to journalArticlepeer-review

    46 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)133-144
    Number of pages12
    JournalDiscrete Applied Mathematics
    Volume57
    Issue number2-3
    Publication statusPublished - 1995

    Fingerprint Dive into the research topics of 'The complexity of harmonious colouring for trees'. Together they form a unique fingerprint.

    Cite this