On Total Chromatic Number of Complete Multipartite Graphs

This paper makes progress towards settling the long-standing conjecture that the total chromatic number \(\chi ''(K)\) of the complete p-partite graph \(K = K(r_1, \dots , r_p)\) is \(\varDelta (K) + 1\) if and only if \(K \ne K_{r,r}\) and if K has an even number of vertices then \(def(K) = \varSigma _{v \in V(K)}(\varDelta (K) - d_K(v))\) is at least the number of parts of odd size. The problem was settled for complete 3-partite graphs by Chew and Yap in 1992, and for complete 4-partite graphs by Dong and Yap in 2000; the difficulty rises manifold with the increase in the number of parts. In 2014, Dalal and Rodger (Graphs and Combinatorics (2015), 1–15) introduced an approach using amalgamations to attack the conjecture and demonstrated its power by settling the problem for complete 5-partite graphs. Their approach required coloring of all the vertices in each part with the same color. However, the applicability of their approach is restricted because, for each \(k \in \mathbb {N}\) , there are complete 2k-partite graphs K for which any total coloring of K in which all the vertices in each part are colored the same would require at least \(\varDelta (K)+2\) colors, although \(\chi ''(K) = \varDelta (K)+1\) . In this paper, we overcome this difficulty by providing a technique that allows the vertices in the same part to have different colors by adapting a result of Bahmanian and Rodger (J. Graph Theory (2012), 297–317) on graph amalgamations. Using our technique, we solve the classification problem for all complete 6-partite graphs.