Total Coloring of Dumbbell Maximal Planar Graphs

The Total Coloring Conjecture (TCC) states that every simple graph G is totally (Delta+2)-colorable, where Delta 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: J9, 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 (Delta+2)-coloring for any I-dumbbell maximal planar graph.

Automated summary

This paper proves the applicability of dumbbell maximal planar graphs to the Total Coloring Conjecture, categorizes them into three types, and proposes an algorithm for computing their coloring properties.