On the total chromatic number of the direct product of cycles and complete graphs

¹ INF, Universidade Federal de Goiás, Goiâania, Brazil
² COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
³ IC, Universidade Federal Fluminense, Niterói, Brazil
⁴ IFG, Instituto Federal de Goiás, Formosa, Brazil
⁵ IME, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil
⁶ LORIA, Université de Lorraine, Vandoeuvre-lès-Nancy, France

^* Corresponding author: patraocaroline@gmail.com

Received: 17 January 2023
Accepted: 15 February 2024

Abstract

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 (called Type 1) or Δ(G) + 2 (called Type 2), where Δ(G) is the maximum degree of G. We consider the direct product of complete graphs K_m × K_n. It is known that if at least one of the numbers m or n is even, then K_m × K_n is Type 1, except for K₂ × K₂. We prove that the graph K_m × K_n is Type 1 when both m and n are odd numbers, by using that the conformable condition is sufficient for the graph K_m × K_n to be Type 1 when both m and n are large enough, and by constructing the target total colorings by using Hamiltonian decompositions and a specific color class, called guiding color. We additionally apply our technique to the direct product C_m × K_n of a cycle with a complete graph. Interestingly, we are able to find a Type 2 infinite family C_m × K_n, when m is not a multiple of 3 and n = 2. We provide evidence to conjecture that all other C_m × K_n are Type 1.