Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors
H.R. Hind, Michael S. O. Molloy, Bruce A. Reed · SIAM Journal on Computing · 1998
We provide a polynomial time algorithm which finds a total coloring of any graph with maximum degree $\D$, $\D$ sufficiently large, using at most $\D+8\log^8\D$ colors. This improves the best previous upper bound on the total chromatic number of $\D+18\D^{1/3}\log(3\D)$.