Total Chromatic Number of Graphs of High Maximum Degree

Abstract

The total chromatic number ${\chi }_T(G)$ of a graph $G$ is the least number of colours needed to colour the edges and vertices of $G$ so that no incident or adjacent elements receive the same colour. This paper shows that if $G$ has maximum degree $\mathrm{\Delta }(G)>\frac{3}{4}|V(G)I–\frac{1}{2}$, then ${\chi }_T(G)\le \mathrm{\Delta }(G)+2$. A slightly weaker version of the result has earlier been proved by Hilton and Hind $[9]$. The proof here is shorter and simpler than the one given in $[9]$.