Total colorings of equibipartite graphs

Abstract The total chromatic number χτ ( 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 χτ ( G ) = Δ ( G ) + 1, where Δ ( 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 , n − E ( J ) is type 1 if and only if J contains a 4-cycle.