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 = Cnk denote the graphs of powers of cycles of order n and length k with 2 ≤ k < ⌊n 2 ⌋. Then, χ″(G) = Δ(G) + 2, if k > n 3 − 1 and n is odd; and Δ(G) + 1, otherwise. 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.