Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors

Authors:
  • HHHugh Hind
    Hugh Hind
  • MMMichael Molloy
    Michael Molloy
  • BRBruce Reed
    Bruce Reed

Abstract
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)$.