The total chromatic number of graphs of even order and high degree Original Research Article

For a given graph G, denote by GΔ the subgraph of G induced by the vertices of maximum degree. The total chromatic number χT(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G≠K2 is of even order, GΔ is a forest, and δ(G)+Δ(G)⩾32(|V(G)|−1) then χT(G)=Δ(G)+1. We also show that for graphs G of even order and δ(G)+Δ(G)⩾32|V(G)|−52 we have that χT(G)⩽Δ(G)+2.