Publication

Abstract : The total chromatic number χ′′(G) is the least number of colors needed to color the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same color. Behzad and Vizing proposed a well-known total coloring conjecture (TCC): χ′′(G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. For the powers of cycles, Campos and de Mello proposed the following conjecture: Let G=Ckn denote the graphs of powers of cycles of order n and length k with 2≤k<⌊n2⌋ . Then, χ′′(G)={Δ(G)+2,Δ(G)+1, if k>n3−1 and n is odd; andotherwise. In this paper, we prove the Campos and de Mello’s conjecture for some classes of powers of cycles. Also, we prove the TCC for complement of powers of cycles.