2019/04/26 by Marthe Bonamy, Théo Pierron, Bonamy, Marthe +3
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.1904.12060
Total coloring is a variant of edge coloring where both vertices and edges\nare to be colored. A graph is totally k-choosable if for any list assignment\nof k colors to each vertex and each edge, we can extract a proper total\ncoloring. In this setting, a graph of maximum degree \Δ needs at least\n\Δ+1 colors. In the planar case, Borodin proved in 1989 that \Δ+2\ncolors suffice when \Δ is at least 9. We show that this bound also holds\nwhen \Δ is 8.\n