The achromatic number of bounded degree trees Original Research Article

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 k2⩾m.