Total Coloring of Dumbbell Maximal Planar Graphs - Yangyang Zhou; Dongyang Zhao; Mingyuan Ma; Jin Xu (Mathematics, 2022)
The Total Coloring Conjecture (TCC) states that every simple graph G is totally <semantics>(Δ+2)</semantics>-colorable, where <semantics>Δ</semantics> denotes the maximum degree of G. In this paper, we prove that TCC holds for dumbbell maximal planar graphs. Especially, we divide the dumbbell maximal planar graphs into three categories according to the maximum degree: <semantics>J9</semantics>, I-dumbbell maximal planar graphs and II-dumbbell maximal planar graphs. We give the necessary and sufficient condition for I-dumbbell maximal planar graphs, and prove that any I-dumbbell maximal planar graph is totally 8-colorable. Moreover, a linear time algorithm is proposed to compute a total <semantics>(Δ+2)</semantics>-coloring for any I-dumbbell maximal planar graph.