Sobre Coloração Total de Grafos Kneser e de Grafos Produto Direto de Completos e de Ciclos

Nesta tese, investigamos o problema de coloração total em três classes de grafos: grafos Kneser, produto direto de grafos completos e produto direto de grafos ciclos. Na classe dos grafos Kneser K(n,s), mostramos que os conexos mais esparsos K(2k-1,k-1), conhecidos como grafos ímpares, são Tipo 1 e provamos que os densos grafos Kneser K(n,2) verificam a TCC quando n é par, ou quando n é ímpar não divisível por 3. Para os casos restantes quando n é ímpar e divisível por 3, obtemos uma coloração total de K(n,2) com Delta(K(n,2)) + 3 cores quando n é equivalente a 3 mod 4, e com  Delta(K(n,2)) + 4 cores quando n é equivalente a 1 mod 4, onde Delta(K(n,2)) é o grau máximo de K(n,2). Além disso, apresentamos uma família infinita de grafos Kneser K(n,2) que possuem índice cromático igual a  Delta(K(n, 2)).

Com relação ao produto direto de grafos completos Km x Kn, é conhecido que se pelo menos um dos números m ou n é par, então Km x Kn é Tipo 1, exceto para K2 x K2. Provamos que o grafo Km x Kn é Tipo 1 quando m e n são ímpares, completando o resultado de que todos os grafos Km x Kn são Tipo 1, exceto para K2 x K2.

Adicionalmente, para o produto direto de ciclos Cm x Cn, casos particulares de Cm x Cn, para m = 3p, 5l e 8l com p >= 2  e  l >= 1, e n >= 3, são conhecidos serem Tipo 1. Este resultado motivou a conjectura de que, exceto para C4 x C4, o produto direto Cm x Cn, para m, n >= 3, é Tipo 1. Usamos técnicas de colagem para provar que todos os Cm x Cn são Tipo 1, exceto C4 x C4. Além disso, investigamos condições que possam nos ajudar a verificar que o produto direto de dois grafos quaisquer alcance o limitante inferior para o número cromático total.