The total chromatic number of regular graphs of high degree

The total chromatic number _χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) ⩾ ₂³|V (G)|+ ₂₃⁶, where d(G) denotes the degree of a vertex in G, then _χT (G) ⩽ d(G) + 2. This work was supported by the Natural Science Foundation of Chongqing Science and Technology Commission (Grant No. 2007BB2123)