Última alteração: 2021-10-18
Resumo
Uma coloração total em um grafo é uma atribuição de cores para seus vértices e arestas de forma que quaisquer dois elementos adjacentes tenham cores distintas. O Problema da Coloração Total é, dado um grafo G, determinar seu número cromático total,X′′(G), que é o menor número de cores para uma coloração total de G. Por definição, X′′(G)≥Δ(G)+1, onde Δ(G) é o maior número de arestas incidentes em um mesmo vértice de G. Quando X′′(G)=Δ(G)+1, o grafo é Tipo 1; quando X′′(G)=Δ(G)+2, o grafo é Tipo 2. A Conjectura da Coloração Total (TCC), que está em aberto desde 1965, diz que X′′(G)≤Δ(G)+2, para qualquer grafo simples G. Decidir se um grafo simples é Tipo 1 é um problema computacionalmente difícil (NP-completo). Campos provou em 2004 que a TCC vale para a k-ésima potência do ciclo C_n, denotada por C_n^k, quando n é par, e n e k são inteiros positivos. Neste trabalho, a técnica de Campos foi modificada e uma coloração total para um subgrafo gerador do C_n^k foi obtida. Considerando esta coloração e n com qualquer paridade, propriedades sobre as listas de cores usadas e disponíveis em cada vértice do grafo são provadas.