The total chromatic number of nearly complete bipartite graphs (Q1179463)

The total chromatic number of a graph \(G\) is the minimum number of colors required to color the vertices and edges of \(G\) so that no two adjacent vertices, no two adjacent edges and no vertex and incident edge receive the same color. Theorem: Let \(J\) be a subgraph with exactly \(e\) edges of the complete bipartite graph \(K_{n,n}\). Let \(j\) be the number of edges in the maximum matching of \(J\). Then the total chromatic number of \(K_{n,n}\backslash E(J)\) equals \(n+2\) if and only if \(e+j\leq n-1\). A similar easier result for \(K_{2n}\) was proved by the author in [Discrete Math. 79, No.\ 2, 169-175 (1990; Zbl 0714.05025)].