Total coloring conjecture for certain classes of graphs (Q2283827)

Summary: 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 \(\chi^{\prime\prime}(G)\), is the minimum number of colors that suffice in a total coloring. \textit{M. Behzad} [Graphs and their chromatic numbers. East Lansing, MI: Michigan State University (PhD Thesis) (1965); in: Combinatorial mathematics and its applications. Proceedings of a conference, held at the Mathematical Institute, Oxford, from 7--10 July, 1969. London-New York: Academic Press. 1--8 (1971; Zbl 0221.05062)] and \textit{V. G. Vizing} [Russ. Math. Surv. 23, No. 6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968)] conjectured that for any graph \(G, \Delta(G) + 1 \leq \chi^{\prime\prime}(G) \leq \Delta(G) + 2\), where \(\Delta(G)\) 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.