An optimal algorithm to totally color some powers of cycle graphs
Alesom Zorzi, Celina M.H. de Figueiredo, Raphael C. S. Machado · Matemática Contemporânea · 2020
The total chromatic number of a graph G, denoted by χ T (G), is the minimum number of colors needed to totally color G.A wellknown bound is χ T (G) ⩾ ∆(G) + 1, where ∆(G) represents the maximum degree of a vertex in G.The total coloring conjecture (TCC) was proposed independently by Behzad and Vizing and states that, for every simple graph G, χ T (G) ⩽ ∆(G) + 2. This conjecture remains open for chordal and powers of cycle graphs.then G is said to be Type 2. The power of the cycle graph C k n has C n as spanning subgraph and additional edges between vertices at distance at most k in C n .Campos and de Mello (A result on the total colouring of powers of cycles, Discrete Appl.Math.(2007), 55, 585-597) proved the TCC C k n , when k = 3 or when n is even.In the same work, Campos and de Mello proposed a conjecture: C k n is Type 2 if n is odd and k > n/3 -1 and is Type 1 otherwise.In the present work, we prove that the conjecture proposed by Campos and de Mello holds for a graph C k n if k = 3 or k = 4, 2000 AMS Subject Classification: 05Cxx and 05C15.