On The Harmonious Colouring of Trees

被引：0

作者：

Aflaki, A. ^{[1
]}

Akbari, S. ^{[1
,2
]}

Eskandani, D. S. ^{[1
]}

Jamaali, M. ^{[1
]}

Ravanbod, H. ^{[1
]}

机构：

[1] Sharif Univ Technol, Dept Math Sci, Tehran, Iran

[2] Inst Studies Theoret Phys & Math, Sch Math, POB 19395-5746, Tehran, Iran

来源：

ARS COMBINATORIA | 2016年 / 128卷

关键词：

Harmonious colouring; Tree;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a simple graph. 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 h(T) = Delta(T) + 1, where Delta(T) denotes the maximum degree of T. Let T-1 and T-2 be two trees of order n(1) and n(2), respectively and F = T-1 boolean OR T-2. In this paper it is shown that if Delta(T-i) = Delta(i) and Delta(i) >= n(i)/2, for i = 1, 2, then h(F) <= Delta(F) + 2. Moreover, if Delta(1) = Delta(2) = Delta >= n(i)/2, for i = 1, 2, then h(F) = Delta + 2.

引用

页码：55 / 62

页数：8