Total colorings of complete multipartite graphs using amalgamations.

This paper makes progress towards settling the long standing conjecture that the total chromatic number χ ′ ′ of the complete p -partite graph K = K (r 1 , ... , r p) is Δ (K) + 1 if and only if K ≠ K r , r and if K has an even number of vertices then Σ v ∈ V (K) (Δ (K) − d K (v)) is at least the number of parts of odd size. The conjecture has been verified by Chew and Yap (1992) when r 1 < r 2 (with parts arranged in non-decreasing order). Using the amalgamation technique, the authors in 2016 verified the conjecture when r 2 < r 3 . Graphs of even order that are fairly close to being regular are the ones for which χ ′ ′ remains in doubt, where the traditional proof techniques have limitations. In this paper, we use the amalgamation technique to provide sufficient condition for K with sizes of the parts differing by at most 1 (closest to being regular) to have χ ′ ′ (K) = Δ (K) + 1. Using this result, we prove that the conjecture holds when r 3 < r 4 . [ABSTRACT FROM AUTHOR]