On the Total Coloring of Graphs Embeddable in Surfaces
Yue Zhao · Journal of the London Mathematical Society · 1999
The paper shows that any graph G with the maximum degree Δ(G) ⩾ 8, which is embeddable in a surface Σ of Euler characteristic χ(Σ) ⩾ 0, is totally (Δ(G)+2)-colorable. In general, it is shown that any graph G which is embeddable in a surface Σ and satisfies the maximum degree Δ(G) ⩾ (20/9) (3−χ(Σ))+1 is totally (Δ(G)+2)-colorable.