## 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 language | English |
---|---|

Article number | P3 |

Pages (from-to) | - |

Number of pages | 9 |

Journal | Electronic Journal of Combinatorics |

Volume | 19 |

Issue number | 1 |

Publication status | Published - 2012 |