Coloração total em grafos potência de ciclo

Abstract

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 < bn/2c, is Type 2 if and only if n is odd and n < 3(k + 1). In particular, the conjecture would imply that, for each 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.