Total Coloring of Dumbbell Maximal Planar Graphs

Yangyang Zhou, Dongyang Zhao, Mingyuan Ma and Jin Xu
Additional contact information
Yangyang Zhou: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Dongyang Zhao: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Mingyuan Ma: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Jin Xu: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

Mathematics, 2022, vol. 10, issue 6, 1-10

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

Keywords: total coloring; dumbbell maximal planar graphs; I-dumbbell maximal planar graphs; dumbbell transformation; total coloring algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/6/912/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/6/912/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:6:p:912-:d:770093

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().