TY - JOUR

T1 - The harmonious chromatic number of bounded degree trees

AU - Edwards, K.

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

PY - 1996

Y1 - 1996

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

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

UR - http://www.scopus.com/inward/record.url?scp=0030550824&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0030550824

SN - 0963-5483

VL - 5

SP - 15

EP - 28

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 1

ER -