Total coloring on power of cycle graphs

A power of cycle graph C k n is the graph obtained from the chordless cycle Cn by adding an edge between any pair of vertices of distance at most k. Power of cycle graphs have been extensively studied in the literature, in particular with respect to coloring problems, and both vertex-coloring and edge-coloring problems have been solved in the class. The total-coloring problem, however, is still open for power of cycle graphs. Although recent works from Campos and de Mello [9] and from Almeida et al. [1] point partial results for specific values of n and k, the totalcoloring problem is far from being solved in the class. One remarkable conjecture from Campos and de Mello [9] states that C k n , with 2 6 k 2, the number of Type 2 graphs is finite and every power of cycle graph C k n with n > 3(k + 1) would be Type 1. We show that for even power of cycle graphs C k n with k > 2 and n > 4k 2 + 2k are Type 1. Moreover, our proof also classifies the graphs power of cycle C k n , with k = 3 and k = 4, and also shows a threshold for the graphs C k n , with k = 5 and k = 7, to be Type 2. We also present a framework to decompose any power of cycle graph into two other power of cycles, an algorithm to generate an equitable conformable total coloring for all the graphs power of cycle that possibly have a equitable total coloring, and an infinite family of power of cycle graphs that have an optimal equitable total coloring.Um grafo Potência de Ciclo C k n é 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 C k n , com 2 6 k 2, o número de grafos Tipo 2 é finito e que todo grafo Potência de Ciclo C k n , 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 > 4k 2 + 2k é Tipo 1. Além disso, utilizando a mesma técnica, classificamos todos os grafos Potência de Ciclo C k n , com k = 3 e k = 4 e também obtemos um limitante para que os grafos Potência de Ciclo C k n , 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 C k n , 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