The total chromatic number of complete multipartite graphs with low deficiency (Q897273)

A total \(k\)-coloring of a graph \(G\) is a coloring of \(V(G)\cup E(G)\) with \(k\) colors such that for any two adjacent or incident elements \(x,y\in V(G)\cup E(G)\), their colors are distinct. The total chromatic number \(\chi^{\prime\prime}(G)\) is the least integer \(k\) for which such a coloring exists. The authors introduce the method of amalgamations to the investigation of \(\chi^{\prime\prime}(G)\) of chosen classes of graphs. In particular they prove that \(\chi^{\prime\prime}(K_{r_1,r_2,r_3,r_4,r_5})=\Delta(K_{r_1,r_2,r_3,r_4,r_5})+1\) for all complete \(5\)-partite graphs \(K_{r_1,r_2,r_3,r_4,r_5}\), where \(1\leq r_1\leq r_2\leq r_3\leq r_4\leq r_5\) and \(\sum_{i=1}^{5}{r_i}\neq 6\).