Total Coloring on Planar Graphs of Nested <i>n</i>-Pointed Stars

SU Rongjin; FANG Gang; ZHU Enqiang; XU Jin

doi:10.11999/JEIT250861

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

SU Rongjin, FANG Gang, ZHU Enqiang, XU Jin. Total Coloring on Planar Graphs of Nested n-Pointed Stars[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250861

Citation:

SU Rongjin, FANG Gang, ZHU Enqiang, XU Jin. Total Coloring on Planar Graphs of Nested n-Pointed Stars[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250861

SU Rongjin, FANG Gang, ZHU Enqiang, XU Jin. Total Coloring on Planar Graphs of Nested n-Pointed Stars[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250861

Citation:

SU Rongjin, FANG Gang, ZHU Enqiang, XU Jin. Total Coloring on Planar Graphs of Nested n-Pointed Stars[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250861

PDF( 3577 KB)

Total Coloring on Planar Graphs of Nested n-Pointed Stars

doi: 10.11999/JEIT250861 cstr: 32379.14.JEIT250861

SU Rongjin^{1, 2},
FANG Gang¹,
ZHU Enqiang^{1
,
,},
XU Jin^{3, 4}

1.
Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510555, China
2.
School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510555, China
3.
School of Computer Science, Beijing 100871, China
4.
Peking University, Beijing 100871, China

Funds: The National Natural Science Foundation of China (62272115, 62541308)

Received Date: 2025-09-02
Accepted Date: 2026-01-12
Rev Recd Date: 2026-01-09

Available Online: 2026-01-24

Abstract

Abstract

Objective Many combinatorial optimization problems can be regarded as graph coloring problems. A classic topic in this field is total coloring, which combines vertex coloring and edge coloring. Previous studies and current research focus on the Total Coloring Conjecture (TCC), proposed in the 1960s. For graphs, including planar graphs, with maximum degree less than six, the correctness of the TCC has been verified through case enumeration. For planar graphs with maximum degree greater than six, the discharging technique has been used to confirm the conjecture by identifying reducible configurations and establishing detailed discharging rules. This method becomes limited when applied to planar graphs with maximum degree exactly six. Only certain restricted classes of graphs have been shown to satisfy the TCC, such as graphs without 4-cycles and graphs without adjacent triangles. More recent work demonstrates that the TCC holds for planar graphs without 4-fan subgraphs and for planar graphs with maximum average degree less than twenty-three fifths. Thus, it remains unclear whether planar graphs with maximum degree six that contain a 4-fan subgraph or have maximum average degree at least twenty-three fifths satisfy the conjecture. To address this question, this paper studies total coloring of a class of planar graphs known as nested n-pointed stars and aims to show that the TCC holds for these graphs. Methods The study relies on theoretical methods, including mathematical induction, constructive techniques, and case enumeration. An n-pointed star is obtained by connecting each edge of an n-polygon (n ≥ 3) to a triangle and then joining the triangle vertices not on the polygon to form a new n-polygon. Repeating this operation produces a nested n-pointed star with l layers, denoted by $ G_{n}^{l} $. These graphs have maximum degree exactly six. Their structural properties, including the presence of 4-fan subgraphs and maximum average degree greater than twenty-three fifths, are established. Induction on the number of layers is then used to show that $ G_{n}^{l} $ has a total 8-coloring: (1) $ G_{n}^{1} $ has a total 8-coloring; (2) Suppose that $ G_{n}^{l-1} $ has a total 8-coloring; (3) prove that $ G_{n}^{l} $ has a total 8-coloring. A graph $ G_{n}^{l} $ is defined as a type I graph if it has a total 7-coloring. When $ n=3k $, constructive arguments show that $ G_{3k}^{l} $ is a type I graph. The value of $ k $ is considered in two cases, $ (k=2m-1) $ and $ (k=2m) $. In both cases, a total 7-coloring of $ G_{3k}^{l} $ is obtained by directly assigning colors to all vertices and edges. Results and Discussions Induction on the number of layers of $ G_{n}^{l} $ that nested n-pointed stars satisfy the Total Coloring Conjecture (Fig. 5). Five colors are assigned to the vertices and edges of $ G_{3k}^{1} $ to obtain a total 5-coloring (Fig. 6(a) and Fig. 8(a)). Two additional colors are then applied alternately to the edges connecting the polygons in layers 1 and 2. This produces a total 7-coloring of $ G_{3k}^{2} $ (Fig. 7(a) and Fig. 9(a)). After a permutation of the colors, another total 7-coloring of $ G_{3k}^{3} $ is obtained (Fig. 7(b) and Fig. 9(b)). The coloring pattern on the outermost layer is identical to that of $ G_{3k}^{1} $, which allows the same extension to construct total 7-colorings for $ G_{3k}^{4},G_{3k}^{5},\cdots ,G_{3k}^{l} $ . Therefore, $ G_{3k}^{l} $ is a type I graph. Conclusions This study verifies that the Total Coloring Conjecture holds for nested n-pointed stars, which have maximum degree six and contain 4-fan subgraphs. It shows that $ G_{3k}^{l} $ is a type I graph. A further question arises regarding whether $ G_{n}^{l} $ is a type I graph when $ n\neq 3k $. A total 7-coloring can be constructed when $ n=4 $ or $ n=5 $, and therefore both $ G_{4}^{l} $ and $ G_{5}^{l} $ are type I graphs. For other values of $ n\neq 3k $, whether $ G_{n}^{l} $ is a type I graph remains open.
- Total coloring,
- Planar graphs,
- Nested n-pointed stars,
- Type I graphs

FullText(HTML)

References(26)

References

[1]	BEHZAD M. Graphs and their chromatic numbers[D]. [Ph. D. dissertation], Michigan State University, 1965.
[2]	VIZING V G. Some unsolved problems in graph theory[J]. Russian Mathematical Surveys, 1968, 23(6): 125–141. doi: 10.1070/RM1968v023n06ABEH001252.
[3]	ROSENFELD M. On the total coloring of certain graphs[J]. Israel Journal of Mathematics, 1971, 9(3): 396–402. doi: 10.1007/BF02771690.
[4]	VIJAYADITYA N. On total chromatic number of a graph[J]. Journal of the London Mathematical Society, 1971, s2-3(3): 405–408. doi: 10.1112/jlms/s2-3.3.405.
[5]	KOSTOCHKA A V. The total coloring of a multigraph with maximal degree 4[J]. Discrete Mathematics, 1977, 17(2): 161–163. doi: 10.1016/0012-365X(77)90146-7.
[6]	KOSTOCHKA A V. The total chromatic number of any multigraph with maximum degree five is at most seven[J]. Discrete Mathematics, 1996, 162(1/3): 199–214. doi: 10.1016/0012-365X(95)00286-6.
[7]	DALAL A, MCDONALD J, and SHAN S L. Total coloring graphs with large maximum degree[J]. Journal of Graph Theory, 2025, 110(3): 249–262. doi: 10.1002/jgt.23268.
[8]	COUTO F, FERRAZ D A, and KLEIN S. New results on edge-coloring and total-coloring of split graphs[J]. Discrete Applied Mathematics, 2025, 360: 297–306. doi: 10.1016/j.dam.2024.09.008.
[9]	DALAL A and PANDA B S. On total chromatic number of complete multipartite graphs[J]. Discrete Applied Mathematics, 2025, 377: 445–458. doi: 10.1016/j.dam.2025.08.027.
[10]	PUNITHA A and JAYARAMAN G. On total coloring of triple star and lobster graphs[J]. Communications on Applied Nonlinear Analysis, 2024, 31(8s): 494–504. doi: 10.52783/cana.v31.1543.
[11]	KAVASKAR T and SUKUMARAN S. Total coloring of some graph operations[C]. The 10th International Conference on Algorithms and Discrete Applied Mathematics, Bhilai, India, 2024: 302–312. doi: 10.1007/978-3-031-52213-0_21.
[12]	PUNITHA A and JAYARAMAN G. Total coloring of middle graph of certain snake graph families[J]. Journal of Applied Mathematics & Informatics, 2024, 42(2): 353–366. doi: 10.14317/jami.2024.353.
[13]	KAVASKAR T and SUKUMARAN S. Total coloring of the generalized corona product of graphs[J]. Studia Scientiarum Mathematicarum Hungarica, 2025, 62(1): 1. doi: 10.1556/012.2025.04326.
[14]	BORODIN O V. On the total coloring of planar graphs[J]. Journal für die reine und angewandte Mathematik, 1989, 1989(394): 180–185. doi: 10.1515/crll.1989.394.180.
[15]	KOWALIK Ł, SERENI J S, and ŠKREKOVSKI R. Total-coloring of plane graphs with maximum degree nine[J]. SIAM Journal on Discrete Mathematics, 2008, 22(4): 1462–1479. doi: 10.1137/070688389.
[16]	YAP H P. Total Colourings of Graphs[M]. Berlin, Heidelberg: Springer, 2006: 96–103. doi: 10.1007/BFb0092895.
[17]	XU Renyu and WU Jianliang. Total coloring of planar graphs with 7-cycles containing at most two chords[J]. Theoretical Computer Science, 2014, 520: 124–129. doi: 10.1016/j.tcs.2013.08.019.
[18]	SANDERS D P and ZHAO Yue. On total 9-coloring planar graphs of maximum degree seven[J]. Journal of Graph Theory, 1999, 31(1): 67–73. doi: 10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C.
[19]	CAI Hua. Total coloring of planar graphs without chordal 7-cycles[J]. Acta Mathematica Sinica, English Series, 2015, 31(12): 1951–1962. doi: 10.1007/s10114-015-4337-y.
[20]	WANG Yingqian, SHANGGUAN M L, and LI Qiao. On total chromatic number of planar graphs without 4-cycles[J]. Science in China Series A: Mathematics, 2007, 50(1): 81–86. doi: 10.1007/s11434-007-2031-x.
[21]	SHEN Lan and WANG Yingqian. On the 7 total colorability of planar graphs with maximum degree 6 and without 4-cycles[J]. Graphs and Combinatorics, 2009, 25(3): 401–407. doi: 10.1007/s00373-009-0843-y.
[22]	SUN Xiangyong, WU Jianliang, WU Yuwen, et al. Total colorings of planar graphs without adjacent triangles[J]. Discrete Mathematics, 2009, 309(1): 202–206. doi: 10.1016/j.disc.2007.12.071.
[23]	ZHU Enqiang and XU Jin. A sufficient condition for planar graphs with maximum degree 6 to be totally 8-colorable[J]. Discrete Applied Mathematics, 2017, 223: 148–153. doi: 10.1016/j.dam.2017.01.036.
[24]	CHANG Yulin, JING Fei, WANG Guanghui, et al. Total-coloring of sparse graphs with maximum degree 6[J]. Acta Mathematicae Applicatae Sinica, English Series, 2021, 37(4): 738–746. doi: 10.1007/s10255-021-1039-3.
[25]	ZHU Enqiang and RAO Yongsheng. A sufficient condition for planar graphs of maximum degree 6 to be totally 7-colorable[J]. Discrete Dynamics in Nature and Society, 2020, 2020(1): 3196540. doi: 10.1155/2020/3196540.
[26]	GEETHA J, NARAYANAN N, and SOMASUNDARAM K. Total colorings-a survey[J]. AKCE International Journal of Graphs and Combinatorics, 2023, 20(3): 339–351. doi: 10.1080/09728600.2023.2187960.