Sobre Coloração Total de Grafos Cúbicos

Um grafo cúbico é dito Tipo 1 se este possui uma coloração total com 4 cores, e Tipo 2 caso contrário; neste caso, sabemos que este possui uma coloração total com 5 cores. Uma coloração total é equilibrada se as cardinalidades de quaisquer duas classes de cor diferem em no máximo 1. Similarmente, sabe-se que todo grafo cúbico possui uma coloração total equilibrada usando no máximo 5 cores.

O estudo de coloração total de grafos cúbicos abordado nesta tese foi motivado pela rica literatura existente e principalmente pela questão proposta por Cavicchioli et al. em 2003 de encontrar, caso exista, o menor snark (grafo cúbico  não 3-aresta-colorível com propriedades adicionais de conectividade) com cintura pelo menos 5 que seja Tipo 2. De um modo geral, o principal objetivo desta tese é confirmar a dificuldade desta questão, através de resultados teóricos e computacionais que sugerem respostas positivas e negativas para a existência de tal grafo, e através da formulação de duas outras questões relacionadas. As duas novas questões abordam a não 4-total-colorabilidade dos grafos cúbicos com cintura pelo menos 5, uma considerando a coloração total e a outra considerando a coloração total equilibrada.

Contribuímos com as três questões acima, exibindo famílias de grafos cúbicos que indicam que as questões devem possuir resposta negativa. Por outro lado, apresentamos famílias de grafos cúbicos não 4-total-coloríveis, como pistas de que as questões devem possuir resposta positiva. Além disso, provamos a NP-completude do problema de determinar se um grafo cúbico bipartido possui uma 4-coloração-total equilibrada e analisamos propriedades gerais de coloração total, incluindo caracterizações de grafos cúbicos Tipo 1 e alguns exemplos pertinentes.