20.500.12556/RUP-22074 A sharp upper bound for the harmonious total chromatic number of graphs and multigraphs Ostra zgornja meja za harmonično totalno barvitost grafov in multigrafov 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 h_t(G). Here, we give a general upper bound for h_t(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 λK_n, 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 ≤ h_t(K_n)≤ 5/3 n + θ(1). In this paper, we prove that h_t(K_n) = ⌈3/2 n⌉ except for h_t(K₁) = 1 and h_t(K₄) = 7; therefore, h_t(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 h_t(G) ≤ (λ-1)(2⌈n/2⌉-1)+⌈3n/2⌉ for n > 4, where G is a multigraph such that λ is the maximum number of edges between any two vertices. total colouring harmonious colouring complete graphs complete multigraphs Levi graph totalno barvanje harmonično barvanje polni grafi polni multigrafi Levijev graf true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2025-11-03 12:19:40 2025-11-03 12:19:40 2025-11-18 03:05:15 0000-00-00 00:00:00 2025 0 0 10 str. no. 3, [article no.] P3.02 Vol 8 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2024-12-12 519.17 2590-9770 10.26493/2590-9770.1752.c31 ADAM_Abreu,Baptist_Gauci,Mattiolo,Mazzuoccolo,Romaniello,Rubio-Montiel,Traetta_2025.pdf ADAM_Abreu,Baptist_Gauci,Mattiolo,Mazzuoccolo,Romaniello,Rubio-Montiel,Traetta_2025.pdf 1 C496415C3AEC0C98F4303E36045C0337 dc5595f01dd8d732cf325a775646658744ea362a035a8222f5567fa594f10188 c64bc28a-b8a7-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32020 Založba Univerze na Primorskem 0 0 0