A sharp upper bound for the harmonious total chromatic number of graphs and multigraphs

Abstract

A proper total colouring of a graph G is called harmonious if it has the further property that when replacing each unordered pair of incident vertices and edgeswith their colours, then no pair of colours appears twice. The smallest number of colours for it to exist is called the harmonious total chromatic number of G, denoted by ht(G). Here, we give a general upper bound for ht(G) in terms of the order n of G. Our two main results are obvious consequences of the computation of the harmonious total chromatic number of the complete graph Kn and of the complete multigraph 位Kn, where 位 is the number of edges joining each pair of vertices of Kn. In particular, Araujo-Pardo et al. have recently shown that 3/2 n鈥勨墹鈥刪t(Kn)鈮� 5/3 n + 胃(1). In this paper, we prove that ht(Kn)鈥�=鈥勨寛3/2 n鈱� except for ht(K鈧�)鈥�=鈥�1 and ht(K鈧�)鈥�=鈥�7; therefore, ht(G)鈮� 鈱�3/2 n鈱�, for every graph G on n鈥�>鈥�4 vertices. Finally, we extend such a result to the harmonious total chromatic number of the complete multigraph 位Kn and as a consequence show that ht(G) 鈮� (位-1)(2鈱坣/2鈱�-1)+鈱�3n/2鈱� for n鈥�>鈥�4, where G is a multigraph such that 位 is the maximum number of edges between any two vertices.