Total Coloring of Dumbbell Maximal Planar Graphs
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>+<...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/6/912 |
| _version_ | 1797445416502951936 |
|---|---|
| author | Yangyang Zhou Dongyang Zhao Mingyuan Ma Jin Xu |
| author_facet | Yangyang Zhou Dongyang Zhao Mingyuan Ma Jin Xu |
| author_sort | Yangyang Zhou |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T13:26:30Z |
| format | Article |
| id | doaj.art-a1cc2b90c1b246bbad1f74a760d8f5a7 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T13:26:30Z |
| publishDate | 2022-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-a1cc2b90c1b246bbad1f74a760d8f5a72023-11-30T21:23:56ZengMDPI AGMathematics2227-73902022-03-0110691210.3390/math10060912Total Coloring of Dumbbell Maximal Planar GraphsYangyang Zhou0Dongyang Zhao1Mingyuan Ma2Jin Xu3School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, ChinaSchool of Electronics Engineering and Computer Science, Peking University, Beijing 100871, ChinaSchool of Electronics Engineering and Computer Science, Peking University, Beijing 100871, ChinaSchool of Electronics Engineering and Computer Science, Peking University, Beijing 100871, ChinaThe 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.https://www.mdpi.com/2227-7390/10/6/912total coloringdumbbell maximal planar graphsI-dumbbell maximal planar graphsdumbbell transformationtotal coloring algorithm |
| spellingShingle | Yangyang Zhou Dongyang Zhao Mingyuan Ma Jin Xu Total Coloring of Dumbbell Maximal Planar Graphs Mathematics total coloring dumbbell maximal planar graphs I-dumbbell maximal planar graphs dumbbell transformation total coloring algorithm |
| title | Total Coloring of Dumbbell Maximal Planar Graphs |
| title_full | Total Coloring of Dumbbell Maximal Planar Graphs |
| title_fullStr | Total Coloring of Dumbbell Maximal Planar Graphs |
| title_full_unstemmed | Total Coloring of Dumbbell Maximal Planar Graphs |
| title_short | Total Coloring of Dumbbell Maximal Planar Graphs |
| title_sort | total coloring of dumbbell maximal planar graphs |
| topic | total coloring dumbbell maximal planar graphs I-dumbbell maximal planar graphs dumbbell transformation total coloring algorithm |
| url | https://www.mdpi.com/2227-7390/10/6/912 |
| work_keys_str_mv | AT yangyangzhou totalcoloringofdumbbellmaximalplanargraphs AT dongyangzhao totalcoloringofdumbbellmaximalplanargraphs AT mingyuanma totalcoloringofdumbbellmaximalplanargraphs AT jinxu totalcoloringofdumbbellmaximalplanargraphs |