# Total Coloring Conjecture for Certain Classes of Graphs
## 1 Introduction  
All the graphs in this paper are finite, simple and connected. The edge chromatic number of a graph \(G\), denoted by \(\chi^{\prime}(G)\), is the smallest number of colors needed to color the edges of \(G\) so that no two adjacent edges share the same color. For any graph \(G\), it clear that from the [PERSON]'s theorem that the edge chromatic number \(\chi^{\prime}(G)\leq\Delta(G)+1\), where \(\Delta(G)\) is the maximum degree of \(G\). If \(\chi^{\prime}(G)=\Delta(G)\) then \(G\) is called class-I graph and if \(\chi^{\prime}(G)=\Delta(G)+1\) then \(G\) is called class-II graph. For example, \(K_{2n}\) is class-I where as \(K_{2n+1}\) is class-II. Also, any bipartite graph is class-I. In a proper total coloring, any two elements that are either adjacent or incident are assigned different colors. The minimum number of colors needed for a proper total coloring is the total chromatic number of \(G\), denoted by \(\chi^{\prime\prime}(G)\). [PERSON] [1,2] and [PERSON] [3] conjectured [also called as the Total Coloring Conjecture (TCC)] that for any graph \(G\) the following inequality holds: \(\Delta(G)+1\leq\chi^{\prime\prime}(G)\leq\Delta(G)+2\). The lower bound is clearly the best possible. A graph \(G\) is said to total colorable if it satisfies TCC. If a graph \(G\) is total colorable with \(\Delta(G)+1\) colors then the graph is called type-I, and if it is total colorable with \(\Delta(G)+2\) colors, then it is type - II. [PERSON] and [PERSON] [4] proved that determining the total chromatic number is NP-hard even for \(\mu\)-regular bipartite graphs, for each fixed \(\mu\geq 3\).  
Graph products were first defined by [PERSON] [5] and [PERSON] [6]. A lot of work was done on various topics related to graph products, but on the other hand there are still many open questions. The TCC was verified for graph products, such as Cartesian and Direct products, of certain classes of graphs. The TCC holds for Cartesian product graphs \(G\) and \(H\), if the TCC holds for each of the graphs \(G\) and \(H\). [PERSON] [7,8] proved that the Cartesian product graphs \(P_{m}\square P_{n}\), \(m,n\geq 2\), except \(P_{2}\square P_{2}\) are of type I. [PERSON] and [PERSON] [9] determined the total chromatic number of some bipartite graphs. The equitable total chromatic number of a graph \(G\) is the smallest integer \(\mu\) for which \(G\) has a total \(\mu\)-coloring such that the number of elements of any two colors differs by at most one. [PERSON] et al. [10] showed that equitable total chromatic number of \(C_{m}\square C_{n}\) is \(\Delta(C_{m}\square C_{n})+1\). [PERSON] and [PERSON] [11]proved that \(\chi^{\prime\prime}(P_{m}\times P_{n})\) and \(\chi^{\prime\prime}(C_{m}\times P_{n})\) are 5. [PERSON] and [PERSON] [12] proved the TCC for generalized Sierpinski graphs. A survey on graph coloring for its types, methods and applications are given in [13]. Recently [14] it is proved that the graphs \(K_{n}\times K_{n}\), \(C_{m}\times C_{n}\) and \(G\boxtimes H\) are type-I graphs, where \(G\) is any bipartite graph. [PERSON] et al. [15] proved that certain classes of Corona product graphs are type-I. In [16], they also proved the TCC for certain classes of product graphs.  
In this paper, we prove the TCC for certain classes of deleted lexicographic product. We obtain results on the total chromatic number for line graphs, which is a subclass of claw-free graphs. Also we obtain the total chromatic number for double graphs. The following theorems are due to Yap [17].  
Theorem 1: _For any complete graph \(K_{n}\), \(\chi^{\prime\prime}(K_{n})=\begin{cases}n,&\text{if $n$ is odd}\\ n+1,&\text{if $n$ is even.}\end{cases}\)_  
Theorem 2: _For any cycle \(C_{n}\), \(\chi^{\prime\prime}(C_{n})=\begin{cases}\Delta(G)+1,&\text{if $n\equiv 0( mod\ 3)$}\\ \Delta(G)+2,&\text{otherwise.}\end{cases}\)_  
Theorem 3: _For any complete bipartite \(K_{m,n}\), \(\chi^{\prime\prime}(G)=\begin{cases}\Delta(G)+1,&\text{if $n\
eq m$}\\ \Delta(G)+2,&\text{if $n=m$.}\end{cases}\)_