The total chromatic number of nearly complete bipartite graphs

AbstractThe total chromatic number χT(G) of a graph G is the least number of colours needed to colour the edges and vertices of G so that no two adjacent vertices receive the same colour, no two edges incident with the same vertex receive the same colour, and no edge receives the same colour as either of the vertices it is incident with. Let n ≥ 1, let J be a subgraph of Kn,n, let e = |E(J)|, and let j(J) be the maximum size (i.e., number of edges) of a matching in J. Then χT(Kn,nE(J)) = n + 2 if and only if e + j ≤ n − 1