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

Ak-total coloringof a graphGis an assignment ofkcolors to the elements (vertices and edges) ofGso that adjacent or incident elements have different colors. The total chromatic number is the smallest integerkfor whichGhas ak-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 ofG. We consider the direct product of complete graphsKm×Kn. It is known that if at least one of the numbersmornis even, thenKm×Knis Type 1, except forK2×K2. We prove that the graphKm×Knis Type 1 when bothmandnare odd numbers, by using that the conformable condition is sufficient for the graphKm×Knto be Type 1 when bothmandnare 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 productCm×Knof a cycle with a complete graph. Interestingly, we are able to find a Type 2 infinite familyCm×Kn, whenmis not a multiple of 3 andn= 2. We provide evidence to conjecture that all otherCm×Knare Type 1.