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

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 2 × K 2 . 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.