Total colorings of equibipartite graphs

The total chromatic number chi(T)(G) of a graph G is the least number of colors needed to color the vertices and the edges of G such that no adjacent or incident pair of elements receive the same color. A simple graph G is called type 1 if chi(T)(G) = Delta(G) + 1, where Delta(G) is the maximum degree of G. In this paper we prove the following conjecture of Chen et al.: An (n - 2)-regular equibipartite graph K-n,K-n - E(J) is type 1 if and only if J contains a 4-cycle. (C) 1999 Elsevier Science B.V. All rights reserved.