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

• DOI: 10.48550/arxiv.2401.09610
• Publication Date: 2024-01-01
• Authors: M. Abreu; John Baptist Gauci; Davide Mattiolo; Giuseppe Mazzuoccolo; F. Romaniello; Christian Rubio-M...; Tommaso Traetta
• Keywords: Multigraph

A proper total colouring of a graph $G$ is called harmonious if it has the further property that when replacing each unordered pair incident vertices and edges with their colours, then no colours appears twice. The smallest number for to exist chromatic $G$, denoted by $h_t(G)$. Here, we give general upper bound $h_t(G)$ in terms order $n$ $G$. Our two main results are obvious consequences computation complete $K_n$ multigraph $\lambda K_n$, where $\lambda$ joining $K_n$. In particular, Araujo-Pardo et al. have recently shown $\frac{3}{2}n\leq h_t(K_n) \leq \frac{5}{3}n +\theta(1)$. this paper, prove $h_t(K_{n})=\left\lceil \frac{3}{2}n \right\rceil$ except $h_t(K_{1})=1$ $h_t(K_{4})=7$; therefore, $h_t(G) \le \left\lceil \right\rceil$, every on $n>4$ vertices. Finally, extend such result K_n$ as consequence show $h_t(\mathcal{G})\leq (\lambda-1)(2\left\lceil\frac{n}{2}\right\rceil-1)+\left\lceil\frac{3n}{2}\right\rceil$ $n>4$, $\mathcal{G}$ maximum between any