# Total Coloring Conjecture for Certain Classes of Graphs
## 2 Deleted Lexicographic Product  
Let \(G\) and \(H\) be two graphs. The _lexicographic product_[18; 19] of graphs \(G\) and \(H\) is the graph \(G\circ H\) whose vertex set is \(V(G)\times V(H)\), and for which \(((g,h),(g^{\prime},h^{\prime}))\) is an edge of \(G\circ H\) precisely if \((g,g^{\prime})\in E(G)\), or \(g=g^{\prime}\) and \((h,h^{\prime})\in E(H)\). The lexicographic product is also known as graph _substitution_, a name that bears witness to the fact that \(G\circ H\) can be obtained from \(G\) by substituting a copy \(H_{g}\) of \(H\) for every vertex \(g\) of \(G\) and then joining all vertices of \(H_{g}\) with all vertices of \(H_{g^{\prime}}\) if \((g,g^{\prime})\in E(G)\). The lexicographic product is associative but not commutative. The total coloring of some classes of lexicographic product graph were discussed in [14]. For example it is proved that \(K_{m}\circ K_{n}\cong K_{mn}\) is type-I if \(m\) and \(n\) are odd other wise type-II. The _deleted lexicographic product_[19] of two graphs \(G\) and \(H\), denoted by \(D_{lex}\)\((G,H)\), is a graph with the vertex set \(V(G)\times V(H)\) and the edge set \(\{((g,h),(g^{\prime},h^{\prime})):(g,g^{\prime})\in E(G)\) and \(h\
eq h^{\prime}\), or \((h,h^{\prime})\in E(H)\) and \(g=g^{\prime}\}\). Similar to lexicographic product, \(D_{lex}(G,H)\) and \(D_{lex}(H,G)\) are not necessarily isomorphic. Figure 1 shows the graph \(D_{lex}(C_{3},C_{4})\). Please note that \(D_{lex}(G,H)=G\circ H\setminus kG\), where \(kG\) denotes the graph consisting of \(k\) vertex disjoint copies of \(G\) and \(G\circ H\setminus kG\) denotes the deletion of \(kG\) from \(G\circ H\). The join of two graphs \(G\) and \(H\), denoted as \(G\lor H\), is obtained by taking \(G\) and \(H\), and adding edges between every vertex of \(G\) to every vertex of \(H\). Let \(G\) and \(H\) be two graphs with \(m\) and \(n\) vertices respectively. \(D_{lex}(G,H)\) can be obtained from \(G\) by substituting a copy \(H_{u}\) of \(H\) for every vertex \(u\) of \(G\) and then joining all vertices \(h\) of \(H_{u}\) with all vertices \(h^{\prime}\) of \(H_{v}\) if \(h\
eq h^{\prime}\) and \((u,v)\in E(G)\). The maximum degree (of this graph) is \(\Delta(D_{lex}(G,H))=\Delta(H)+(n-1)\Delta(G)\). It is easy to see that \(D_{lex}(P_{1},G)\cong G\). Theorem 4: _For any total colorable graph \(G\), \(K_{2}\circ G\) is total colorable._  
Proof: The graph \(K_{2}\circ G\cong G\lor G\)[14]. Denote the two copies of \(G\) by \(G_{1}\) and \(G_{2}\). The maximum degree of \(G\lor G\) is \(\Delta(G\lor G)=\Delta(G)+n\), where \(n\) is the order of \(G\). Color the elements (vertices and edges) of \(G_{1}\) using colors \(1,...,\Delta(G)+2\). Assign \(n\) new colors to the vertices of \(G_{2}\) and color the edges of \(G_{2}\) as the edge coloring of \(G_{1}\). Here, the corresponding vertices in \(G_{1}\) and \(G_{2}\) have common missing colors from \(\{1,...,\Delta(G)+2\}\). Now, assign a common missing color to the edges (all edges together give one \(1\)-factor of \(G\lor G\)) between the corresponding vertices. At each vertex in \(G_{2}\), there are available colors among the \(n\) vertex colors and using these available colors we color the remaining join edges between \(G_{1}\) and \(G_{2}\). The above theorem can be extended to any bipartite graph. Corollary 1: Let \(G\) be a bipartite graph and \(H\) be a total colorable graph then \(G\circ H\) is total colorable. Proof: Let us consider the graph \(G\circ H\), where \(G\) is bipartite. Let \(X\) and \(Y\) be the two vertex partitions of \(G\). Color all the elements of the layer \(H_{x}\) for all \(x\in X\) as \(H_{0}\) and all the elements of \(H_{y}\) for all \(y\in Y\) as \(H_{1}\). Please note that all the vertices of \(G\circ H\) are properly colored. Since \(G\) is bipartite, the edges of \(G\) can be colored with \(\Delta(G)\) colors. Moreover, in any edge coloring of \(G\) with \(\Delta(G)\) colors each major vertex (vertex with maximum degree) is incident with an edge of each color.