| Summary: | The Total Coloring Conjecture (TCC) states that every simple graph <i>G</i> is totally <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mo>Δ</mo><mo>+</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-colorable, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Δ</mo></semantics></math></inline-formula> denotes the maximum degree of <i>G</i>. 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: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>J</mi><mn>9</mn></msub></semantics></math></inline-formula>, 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mo>Δ</mo><mo>+</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-coloring for any I-dumbbell maximal planar graph.
|
|---|