The achromatic number of bounded degree trees

TY - JOUR

T1 - The achromatic number of bounded degree trees

AU - Cairnie, N.

AU - Edwards, K.

N1 - Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0041783276

M3 - Article

AN - SCOPUS:0041783276

SN - 0012-365X

VL - 188

SP - 87

EP - 97

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -