On Harmonious Colouring of Trees

A. Aflaki, S. Akbari, K. J. Edwards, D. S. Eskandani, M. Jamaali, H. Ravanbod

    Research output: Contribution to journalArticle

    6 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Article numberP3
    Pages (from-to)-
    Number of pages9
    JournalElectronic Journal of Combinatorics
    Volume19
    Issue number1
    Publication statusPublished - 2012

    Cite this