Sobre o número cromático total do produto direto de ciclos e grafos completos

Uma coloração k-total de um grafo G é uma atribuição de k cores aos elementos (vértices e arestas) de G de forma que elementos adjacentes ou incidentes tenham cores diferentes. O número cromático total é o menor inteiro k para o qual G possui uma coloração k-total. A bem conhecida Conjectura da Coloração Total afirma que o número cromático total de um grafo é Δ( G ) + 1 (chamado Tipo 1) ou Δ( G ) + 2 (chamado Tipo 2), onde Δ( G ) é o grau máximo de G. Consideramos o produto direto de grafos completos K m × K n. É sabido que, se pelo menos um dos números m ou n é par, então K m × K n é do Tipo 1, exceto para K 2 × K 2. Provamos que o grafo K m × K n é do Tipo 1 quando tanto m quanto n são números ímpares, utilizando que a condição conformável é suficiente para que o grafo K m × K n seja do Tipo 1 quando tanto m quanto n são grandes o suficiente, e ao construir as colorações totais-alvo usando decomposições Hamiltonianas e uma classe de cor específica, chamada de cor guia. Além disso, aplicamos nossa técnica ao produto direto C m × K n de um ciclo com um grafo completo. Curiosamente, conseguimos encontrar uma família infinita Tipo 2 C m × K n, quando m não é múltiplo de 3 e n = 2. Fornecemos evidências para conjecturar que todos os outros C m × K n são do Tipo 1.