The achromatic number of bounded degree trees

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.