On total coloring the direct product of complete graphs
Diane Castonguay, Celina M.H. de Figueiredo, Luis Antônio Brasil Kowada, Caroline Patrão, Diana Sasaki, Mario Valencia-Pabon · Procedia Computer Science · 2021
A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. We consider the direct product of complete graphs Km × Kn. It is known that if at least one of the numbers m or n is even, then Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1, except when m = n = 2. We prove that the graph Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1 when both m and n are odd numbers, ensuring in this way that all graphs Km × Kn have total chromatic number equal to ∆ (Km × Kn) + 1, except when m = n = 2.