Every planar graph with Δ≥ 8 is totally (Δ+2)-choosable

04/26/2019
by   Marthe Bonamy, et al.
0

Total coloring is a variant of edge coloring where both vertices and edges are to be colored. A graph is totally k-choosable if for any list assignment of k colors to each vertex and each edge, we can extract a proper total coloring. In this setting, a graph of maximum degree Δ needs at least Δ+1 colors. In the planar case, Borodin proved in 1989 that Δ+2 colors suffice when Δ is at least 9. We show that this bound also holds when Δ is 8.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset