Coloração Total em Grafos Potência de Ciclo

Um grafo Potência de Ciclo Ckn é um grafo obtido de um ciclo sem cordas Cn adicionando arestas entre todos os vértices à distância de no máximo k. Os grafos Potência de Ciclo têm sido extensivamente estudados na literatura, principalmente quando tratamos de problemas de coloração. Problemas clássicos, como Coloração de Vértices e Coloração de Arestas, foram totalmente resolvidos nos grafos Potência de Ciclo [7, 32]. Entretanto, o problema da Coloração Total permanece aberto para esta classe de grafos. E mesmo que os trabalhos de Campos e de Mello [9] e de Almeida et al. [1] mostrem avanços significativos para valores específicos de n e k, o problema da Coloração Total está longe de ser resolvido para a classe. Uma conjectura notável, proposta por Campos e de Mello [9], estabelece que Ckn, com 2 =< k < b (n/2), é Tipo 2 se e somente se n é ímpar e n < 3(k + 1), caso contrário é Tipo 1. Em particular, esta conjectura implica que, para cada k >= 2, o número de grafos Tipo 2 é finito e que todo grafo Potência de Ciclo Ckn, com n >= 3(k + 1), é Tipo 1. No presente trabalho, mostramos que todo grafo Potência de Ciclo com k par, k >= 2 e n >= 4k2 + 2k é Tipo 1. Além disso, utilizando a mesma técnica, classificamos todos os grafos Potência de Ciclo Ckn, com k = 3 e k = 4 e também obtemos um limitante para que os grafos Potência de Ciclo Ckn, com k = 5 e k = 7, sejam Tipo 2. Também apresentamos um algoritmo para gerar uma Coloração Harmônica Equilibrada para os grafos Potência de Ciclo Ckn, com n par ou n ímpar e n >= 3(k + 1), em um passo necessário para a construção de uma Coloração Total Equilibrada Tipo 1. Ademais, apresentamos uma família infinita de grafos Potência de Ciclo em que a Coloração Total Equilibrada é ótima.