Even-power of Cycles With Many Vertices are Type 1 Total Colorable
Alesom Zorzi, Celina M.H. de Figueiredo, Raphael C. S. Machado, Uéverton S. Souza · Electronic Notes in Theoretical Computer Science · 2019
A power of cycle graph C n k is the graph obtained from the chordless cycle C n 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. A graph G is Type 1 if can be totally colored with Δ( G ) + 1 colors and is Type 2 if can not be colored with Δ( G )+1 and can be colored with Δ( G )+2, with Δ( G ) representing the maximum degree of a vertex in G . Although recent works from Campos and de Mello [C.N. Campos and C.P. de Mello. A Result on the Total Colouring of Powers of Cycles . Discrete Applied Mathematics, 155 , (2007), 585–597.] and from Almeida et al. [S.M. Almeida, J.T. Belotti, M.M. Omai, and J.F.H. Brim. The Total Coloring of the 3rd and 4th Powers of Cycles . Presented at VI Latin American Workshop on Cliques in Graphs (2014).] point partial results for specific values of n and k , the total-coloring problem is far from being solved in the class. One remarkable conjecture from Campos and de Mello [C.N. Campos and C.P. de Mello. A Result on the Total Colouring of Powers of Cycles . Discrete Applied Mathematics, 155 , (2007), 585–597.] states that C n k , with 2 ≤ k < ⌊ n/ 2⌋, 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 n k with n ≥ 3( k + 1) would be Type 1. We address Campos and de Mello conjecture for power of cycle graphs and we prove a weaker version of the conjecture for even-power of cycle graphs: every C n k with even k ≥ 2 and n ≥ 4 k 2 + 2 k is Type 1. Our proof is actually stronger and shows that, for each even k < ⌊ n/ 2⌋, the number of Type 2 power of cycle graphs C n k is at most 2 k 2 − k . Our results, therefore, constitute a strong evidence in favor of Campos and de Mello conjecture for power of cycle graphs.