# Total Coloring Conjecture for Certain Classes of Graphs
## 3 Line Graphs and Double Graphs
#### Line Graphs  
The _line graph_ of \(G\), denoted by \(L(G)\), has the set \(E(G)\) as its vertex set and two distinct vertices \(e_{1},e_{2}\in V(L(G))\) are adjacent if and only if they share a common vertex in \(G\). Characterization of line graphs are given in [22] including a forbidden subgraph characterization. Figure 2 shows the line graph of \(K_{4}\) and a total coloring with 5 colors. The following are easy observations: (i). We know that the line graph of a path of length \(m\) is again a path of length \(m-1\) and the line graph of a cycle is again a cycle of the same length. Therefore, it is easy to find the total chromatic number for \(L(P_{n})\) and \(L(C_{n})\) (see Theorem 2). (ii). A complete bipartite graph is not always type-I (see Theorem 3). We know that \(L(K_{m,n})\cong K_{m}\Box K_{n}\) and \(K_{m}\Box K_{n}\) is type-I if \(n\) and \(m\) are even and \(m\geq n\geq 4,m\equiv 0\) (mod 4) or \(m>n\geq 4,m\equiv 2\) (mod 4) and \(K_{m}\Box K_{n}\) is type-II if \(m\) is even and \(n\) is odd and \(m>(n-1)^{2}\)[23; 24]. The TCC is open for other cases.  
Theorem 4.1: _For \(n\leq 4\), \(\chi^{\prime\prime}(L(K_{n}))=\Delta(L(K_{n}))+1\)._  
Proof: For \(n=2\), \(L(K_{2})=K_{1}\) and \(\chi^{\prime\prime}(K_{1})=\Delta(K_{1})+1\). And \(n=3\), \(L(K_{3})\cong K_{3}\), \(\chi^{\prime\prime}(K_{3})=\Delta(K_{3})+1\). Also, \(\chi^{\prime\prime}(L(K_{4}))=\Delta(L(K_{4}))+1\). The total coloring of \(L(K_{4})\) is given in Figure 2.  
From the Theorem 1, we know that \(K_{n}\) is type-I if \(n\) is odd and it is type-II if \(n\) is even. We believe that \(L(K_{n})\) is always type-I. In this regard, we proposed the following conjecture.  
**Conjecture**: For any complete graph \(K_{n}\), \(\chi^{\prime\prime}(L(K_{n}))=2n-3\).  
The double graph \(D(G)\) of a given graph \(G\) is constructed by making two copies of \(G\) (including the initial edge set of each) and adding edges \(((u,1),(v,2))\) and \(((v,1),(u,2))\) for every edge \(uv\) of \(G\). [PERSON] et al. [25] studied various properties of double graphs.  
Theorem 4.2: _For any total colorable graph \(G\),_  
\[\chi^{\prime\prime}(D(G))\begin{cases}=\Delta(D(G))+1&\text{if $G$ is type I}\\ \leq\Delta(D(G))+2&\text{if $G$ is type II}.\end{cases}\]  
Proof: Here, \(\Delta(D(G))=2\Delta(G)\).  
Suppose \(G\) is type I.  
Color the elements of two copies of \(G\) using \(\Delta(G)+1\) colors. The two vertices in \(D(G)\) are adjacent only if the corresponding vertices are adjacent in \(G\). The remaining uncolored edges in \(D(G)\) will form \(\Delta(G)\) matchings, these edges can be colored with additional \(\Delta(G)\) colors since they induce a bipartite graph with partition sets corresponding to the vertex sets of the two copies of \(G\).  
Suppose \(G\) is type II.  
Color the elements of two copies of \(G\) using \(\Delta(G)+2\) colors. Again the remaining uncolored edges will form \(\Delta(G)\) matchings. In this coloring assignment, two adjacent vertices in \(D(G)\) will receive different vertex colors. We color the remaining edges using addtional \(\Delta(G)\) colors.  
Hence the proof.  
Conceptualization, R.V., J.G. and K.S.; Methodology, R.V., J.G. and K.S.; Software, R.V.; Validation, R.V., J.G. and K.S.; Formal Analysis, R.V., J.G. and K.S; Investigation, R.V., J.G. and K.S; Resources, J.G. and K.S.; Writing--Original Draft Preparation, R.V., J.G. and K.S.; Writing--Review & Editing, R.V., J.G. and K.S.; Visualization, R.V., J.G. and K.S.; Supervision, J.G. and K.S.; Project Administration, K.S.; Funding Acquisition, K.S.  
This research work is supported by SERB-DST (Grant SR/S4/MS: 867/14).  
We are grateful to the reviewers for their valuable and helpful comments which lead to the improvement of this paper.  
The authors declare no conflict of interest.