Publication Type:

Journal Article


Algorithms, Multidisciplinary Digital Publishing Institute, Volume 11, Number 10, p.161 (2018)



deleted lexicographic product, double graph, Lexicographic product, Line graph, Total coloring


A total coloring of a graph G is an assignment of colors to the elements of the graph G such that no two adjacent or incident elements receive the same color. The total chromatic number of a graph G, denoted by , is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any graph G, , where is the maximum degree of G. In this paper, we prove the total coloring conjecture for certain classes of graphs of deleted lexicographic product, line graph and double graph.

Cite this Research Publication

R Vignesh, Geetha, J., and Dr. Somasundaram K., “Total Coloring Conjecture for Certain Classes of Graphs”, Algorithms, vol. 11, p. 161, 2018.