# Total Coloring Conjecture for Certain Classes of Graphs
## 2 Deleted Lexicographic Product
Consider the set \(F\) of all edges of \(G\) of an arbitrary fixed color. For each edge \(xy\in F\) color the edges between \(H_{x}\) and \(H_{y}\) in \(G\circ H\) as in \(K_{2}\circ H\). So far, \(\left|F\right|\) copies of \(K_{2}\circ H\) and the remaining \(\left|V(G)\right|-2\left|F\right|\) layers \(H_{y}\) are colored in \(G\circ H\) using at most \(\Delta(K_{2}\circ H)+2\) colors. The uncolored edges induce a bipartite graph of maximum degree \(\Delta(G\circ H)-\Delta(K_{2}\circ H)=n(\Delta(G)-1)\) which implies that they can be colored with this number of additional colors. Hence \(\chi^{\prime\prime}(G\circ H)\leq\Delta(K_{2}\circ H)+2+n(\Delta(G)-1)=\Delta (G\circ H)+2\). Therefore TCC holds for \(G\circ H\). The above theorem and corollary can be extended to deleted lexicographic product. In the following theorem, we prove the total coloring conjecture for deleted lexicographic product of two large classes of graphs. Theorem 4.1: _For any class-I graph \(G\) and a graph \(H\) with at least 3 vertices, \(D_{lex}(G,H)\) is total colorable. In particular, if \(H\) is class-I then \(D_{lex}(G,H)\) is also type-I._  
Proof: Let \(H\) be a graph with \(n\) vertices, \(n\geq 3\). The maximum degree of \(D_{lex}(G,H)\) is \(\Delta(D_{lex}(G,H))=\Delta(H)+(n-1)\Delta(G)\). Assign \(\Delta(H)+1\) colors to the edges and \(n\) colors to all the vertices of all the copies of \(H\). Now, each edge \((u,v)\) in \(G\) gives a set of join edges between the copies \(H_{u}\) and \(H_{v}\). Since \(G\) is class-I graph, the edges are partitioned into \(\Delta(G)\) independent sets. Correspondingly, the join edges between the copies of \(H\) are partitioned into \(\Delta(G)\) sets \(P_{1},P_{2},...,P_{\Delta(G)}\). Since \(n\geq 3\), there are \(n-1\) available colors at each vertex in each copy of \(H\). Using these available colors we color the join edges in \(P_{1}\) and using the remaining \((n-1)(\Delta(G)-1)\) unused colors, we color the join edges in the remaining partitions. This is same as problem of finding a perfect rainbow matching in \(K_{n,n}\)[20]. Therefore we used \(\Delta(H)+1+n+(n-1)(\Delta(G)-1)=\Delta(D_{lex}(G,H))+2\) colors for the total coloring of \(D_{lex}(G,H)\). Hence \(D_{lex}(G,H)\) satisfy the TCC. If \(H\) is class-I then assign \(\Delta(H)\) colors to the edges in all the copies of \(H\) and remaining elements are colored as in above. Therefore \(D_{lex}(G,H)\) is type-I. We know that any bipartite graph is class-I and any regular graph with even order is also class-I. Based on these facts, we have the following two corollaries. For any bipartite graph \(G\) and a graph \(H\) with at least 3 vertices, \(D_{lex}(G,H)\) is total colorable. In particular, if \(H\) is class-I then \(D_{lex}(G,H)\) is type-I. If \(G\) is a regular graph with even order and \(H\) is any graph with at least 3 vertices then \(D_{lex}(G,H)\) is total colorable. In particular, if \(H\) is class-I then \(D_{lex}(G,H)\) is type-I. In Theorem 3.1, we can obtain the tight bound for certain classes of \(G\). For example, it is easy to see that \(D_{lex}(P_{2},P_{n})\) is type-I graph. Also, in Theorem 3.1 either \(G\) or \(H\) must have at least three vertices. For example, we know that \(P_{2}\) is class-I graph and \(D_{lex}(P_{2},P_{2})\cong C_{4}\) and \(C_{4}\) is type-II (see Theorem 3.1). There are classes of graphs \(G\) and \(H\) such that \(D_{lex}(G,H)\) may be type-II. For example, consider the graph \(D_{lex}(P_{2},C_{2n+1})\), \(n\geq 3\), \(D_{lex}(P_{2},C_{2n+1})\cong C_{2n+1}\lor C_{2n+1}-F\), where \(F\) is the one factor \(\{(u_{i},u_{i})|i=1,2,...,2n+1\}\). Here the maximum degree is \(2(n+1)\). Vertices in each cycles are colored with \(2n+1\) colors and the join edges are colored with the same \(2n+1\) colors with a proper permuation of colors. Also, the edge colorings of any odd cycle requires 3 colors. Therefore \(2n+3\) colors are not sufficient to color the elements of \(D_{lex}(P_{2},C_{2n+1})\). Hence \(D_{lex}(P_{2},C_{2n+1})\) is type-II.