Total coloring of circulant graphs $C_{n}(1, 4)$

Year 2025, Volume: 54 Issue: 6, 2269 - 2277, 30.12.2025

Senyuan Su , Chunling Tong , Yuansheng Yang

https://doi.org/10.15672/hujms.1404223

Abstract

Total coloring of circulant graphs has attracted much attention in recent years. Studies on the total chromatic numbers of them, in particular 4-regular circulant graphs, have thrown up a number of interesting results. However, as a challenging issue, the total chromatic numbers of 4-regular circulant graphs $C_{n}(1, 4)$ remain an open question even after many efforts. In this paper, we solve this question by completely determining total chromatic numbers of $C_{n}(1, 4)$ for all $n\geq 9$.

Keywords

total chromatic number , total coloring , circulant graph

Project Number

Shandong Provincial Natural Science Foundation (No. ZR2020KF010)

Thanks

We are grateful to Bojan Mohar for his helpful suggestion.

References

• [1] M. Behzad, Graphs and their chromatic numbers, PhD thesis, Michigan State University, 1965.
• [2] C.N. Campos and C.P. de Mello, A result on the total colouring of powers of cycles, Discret. Appl. Math. 155(5), 585–597, 2007.
• [3] C.N. Campos and C.P. de Mello, Total colouring of $C^2_n$ , Trends Comput. Appl. Math. 4(2), 177-186, 2003.
• [4] A.G. Chetwynd and A.J.W. Hilton, Some refinements of the total chromatic number conjecture, Congr. Numerantium 66, 195-216, 1988.
• [5] J. Geetha, N. Narayanan and K. Somasundaram, Total colorings-a survey, AKCE Int. J. Graphs Comb. 20(3), 339-351, 2023.
• [6] J. Geetha, K. Somasundaram and H.L. Fu, Total coloring of circulant graphs, Discret. Math. Algorithms Appl. 13(5), 2150050, 2021.
• [7] R. Khennoufa and O. Togni, Total and fractional total colourings of circulant graphs, Discrete Math. 308(24), 6316–6329, 2008.
• [8] A.V. Kostochka, The total coloring of a multigraph with maximal degree 4, Discrete Math. 17(2), 161–163, 1977.
• [9] C.J.H. McDiarmid and A. Sánchez-Arroyo, Total coloring regular bipartite graphs is NP-hard, Discrete Math. 124(1-3), 155–162, 1994.
• [10] R. Navaneeth, J. Geetha, K. Somasundaram and H.L. Fu, Total colorings of some classes of four regular circulant graphs, AKCE Int. J. Graphs Comb. 21(1), 1-3, 2024.
• [11] M. Nigro, M.N. Adauto and D. Sasaki, On total coloring of 4-regular circulant graphs, Procedia Comput. Sci. 195, 315–324, 2021.
• [12] S. Prajnanaswaroopa, J. Geetha, K. Somasundaram, H.L. Fu, and N. Narayanan, On total coloring of some classes of regular graphs, Taiwan. J. Math. 26(4), 667-683, 2022.
• [13] A. Sánchez-Arroyo, Determining the total colouring number is NP-hard, Discrete Math. 78(3), 315–319, 1989.
• [14] C.L. Tong, X.H. Lin, Y.S. Yang and Z.H. Li, Equitable total coloring of $C_m \Box C_n$, Discret. Appl. Math. 157(4), 596–601, 2009.
• [15] C.L. Tong, X.H. Lin and Y.S. Yang, Equitable total coloring of generalized Petersen graphs $P(n,k)$, Ars Comb. 143, 321-336, 2019.
• [16] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Math. Nauk 23(6), 117–134, 1968.