The harmonious chromatic number of bounded degree trees

    Research output: Contribution to journalArticle

    13 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. Let d be a fixed positive integer. We show that there is a natural number N(d) such that if T is any tree with m = N(d) edges and maximum degree at most d, then the harmonious chromatic number h(T) is k or k + 1, where k is the least positive integer such that (k/2) = m. We also give a polynomial time algorithm for determining the harmonious chromatic number of a tree with maximum degree at most d.
    Original languageEnglish
    Pages (from-to)15-28
    Number of pages14
    JournalCombinatorics, Probability and Computing
    Volume5
    Issue number1
    Publication statusPublished - 1996

    Fingerprint Dive into the research topics of 'The harmonious chromatic number of bounded degree trees'. Together they form a unique fingerprint.

  • Cite this