On Harmonious Colouring of Trees

TY - JOUR

T1 - On Harmonious Colouring of Trees

AU - Aflaki, A.

AU - Akbari, S.

AU - Edwards, K. J.

AU - Eskandani, D. S.

AU - Jamaali, M.

AU - Ravanbod, H.

PY - 2012

Y1 - 2012

N2 - Let G be a simple graph and Delta(G) denote the maximum degree of G. A harmonious colouring of 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. In this paper it is shown that if T is a tree of order n and Delta(T) > n/2, then there exists a harmonious colouring of T with Delta(T) + 1 colours such that every colour is used at most twice. Thus h(T) = Delta(T) + 1. Moreover, we prove that if T is a tree of order n and Delta(T) <= [n/2], then there exists a harmonious colouring of T with [n/2] + 1 colours such that every colour is used at most twice. Thus h(T) <= [n/2] + 1.

AB - Let G be a simple graph and Delta(G) denote the maximum degree of G. A harmonious colouring of 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. In this paper it is shown that if T is a tree of order n and Delta(T) > n/2, then there exists a harmonious colouring of T with Delta(T) + 1 colours such that every colour is used at most twice. Thus h(T) = Delta(T) + 1. Moreover, we prove that if T is a tree of order n and Delta(T) <= [n/2], then there exists a harmonious colouring of T with [n/2] + 1 colours such that every colour is used at most twice. Thus h(T) <= [n/2] + 1.

M3 - Article

SN - 1077-8926

VL - 19

SP - -

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P3

ER -