Total coloring graphs with large maximum degree

Abstract

We prove that for any graph $G$, the total chromatic number of $G$ is at most $\hat{I}”(G)+2\lceil \frac{|V(G)|}{\hat{I}”(G)+1}\rceil$. This saves one color in comparison with a result of Hind from 1992. In particular, our result says that if $\hat{I}”(G)\ge \frac{1}{2}|V(G)|$, then $G$ has a total coloring using at most $\hat{I}”(G)+4$ colors. When $G$ is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any $0<\epsilon <1$, there exists $n_0\in \mathbb{N}$ such that: if $G$ is an $r$-regular graph on $n\ge n_0$ vertices with $r\ge \frac{1}{2}(1+\epsilon )n$, then $\ddot{I}{‡}_T(G)\le \hat{I}”(G)+2$. This confirms the Total Coloring Conjecture for such graphs $G$.