The achromatic number of bounded degree trees

N. Cairnie, K. Edwards

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)

    Abstract

    The achromatic number ?(G) of a simple graph G is the largest number of colours possible in a proper vertex colouring of G in which each pair of colours appears on at least one edge. The problem of determining the achromatic number of a tree is known to be NP-hard (Cairnie and Edwards, 1997). In this paper, we present a polynomial-time algorithm for determining the achromatic number of a tree with maximum degree at most d, where d is a fixed positive integer. Prior to giving this algorithm, 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 ?(T) is k or k - 1, where k is the largest integer such that ()=m.
    Original languageEnglish
    Pages (from-to)87-97
    Number of pages11
    JournalDiscrete Mathematics
    Volume188
    Issue number1-3
    Publication statusPublished - 1998

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

    Cite this