Total-Coloring of Plane Graphs with Maximum Degree Nine

Abstract

The central problem of the total-colorings is the total-coloring conjecture, which asserts that every graph of maximum degree $\Delta$ admits a $(\Delta+2)$-total-coloring. Similar to edge-colorings—with Vizing's edge-coloring conjecture—this bound can be decreased by 1 for plane graphs of higher maximum degree. More precisely, it is known that if $\Delta\ge10$, then every plane graph of maximum degree $\Delta$ is $(\Delta+1)$-totally-colorable. On the other hand, such a statement does not hold if $\Delta\le3$. We prove that every plane graph of maximum degree 9 can be 10-totally-colored.