Graphs that embedded in any fixed surfaces with sufficiently large maximum degree $ \Delta $ is total-$ (\Delta +1) $-colorable

Qiming Fang; Li Zhang; Qiming Fang; Li Zhang

doi:10.3934/math.2024075

AIMS Mathematics

2024, Volume 9, Issue 1: 1523-1534. doi: 10.3934/math.2024075

Previous Article Next Article

Research article Special Issues

Graphs that embedded in any fixed surfaces with sufficiently large maximum degree $ \Delta $ is total-$ (\Delta +1) $-colorable

Qiming Fang ^{1
,
,},
Li Zhang ^{2
,
,}

1.
Beijing International Cener for Mathematical Research, Peking University, Beijing 100091, China
2.
School of Mathematical Sciences, Tongji University, Shanghai 200092, China

Received: 03 September 2023 Revised: 16 November 2023 Accepted: 21 November 2023 Published: 11 December 2023
MSC : 05C10

Let $ G $ be a graph that can be embedded in a surface $ \Sigma $ of Euler characteristic $ c'(\Sigma) $. In this paper, we proved that there exists an integer $ \Delta_0 = 4\cdot (5+\sqrt{49-24c'})\cdot [2-c'+\frac{1}{2} (5+\sqrt{49-24c'})] $ such that the total chromatic number of $ G $ is $ \Delta(G) +1 $ if $ \Delta(G) \geq \Delta_0 $.
- total coloring,
- Euler characteristic,
- surface,
- maximum degree,
- algebraic topology
Citation: Qiming Fang, Li Zhang. Graphs that embedded in any fixed surfaces with sufficiently large maximum degree $ \Delta $ is total-$ (\Delta +1) $-colorable[J]. AIMS Mathematics, 2024, 9(1): 1523-1534. doi: 10.3934/math.2024075

Related Papers:

Abstract

Let $ G $ be a graph that can be embedded in a surface $ \Sigma $ of Euler characteristic $ c'(\Sigma) $. In this paper, we proved that there exists an integer $ \Delta_0 = 4\cdot (5+\sqrt{49-24c'})\cdot [2-c'+\frac{1}{2} (5+\sqrt{49-24c'})] $ such that the total chromatic number of $ G $ is $ \Delta(G) +1 $ if $ \Delta(G) \geq \Delta_0 $.

References

[1]	M. Armstrong, Basic Topology, Berlin: Springer-Verlag, 1983. https://doi.org/10.1007/978-1-4757-1793-8
[2]	J. Bondy, U. Murty, Graph Theory, Berlin: Springer Press Graduate Texts in Mathematics (GTM244), 2008. https://doi.org/doi:10.1007/978-1-84628-970-5
[3]	M. Behzad, Graphs and their chromatic numbers, Ph.D thesis, Michigan State University, 1965. https://doi.org/doi:10.25335/M5H41K22C
[4]	O.V. Borodin, Coupled colorings of graphs on a plane, Metody Diskret. Analiz, in Russian, 45 (1987), 21–27.
[5]	O. V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math., 394 (1989), 180–185. https://doi.org/10.1515/crll.1989.394.180 doi: 10.1515/crll.1989.394.180
[6]	O. V. Borodin, A. V. Kostochka, D. R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B, 71 (1997), 184–204. https://doi.org/10.1006/jctb.1997.1780 doi: 10.1006/jctb.1997.1780
[7]	O. V. Borodin, A. V. Kostochka, D. R. Woodall, Total colourings of planar graphs with large maximal degree, J. Graph Theory, 26 (1997), 53–59. https://doi.org/10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO;2-G doi: 10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO;2-G
[8]	T. R. Jensen, B. Toft, Graph Coloring Problems, Hoboken: Wiley Interscience, 1995.
[9]	A. V. Kostochka, The total coloring of a multigraph with maximal degree 4, Discrete Math., 17 (1977), 161–163. https://doi.org/10.1016/0012-365X(77)90146-7 doi: 10.1016/0012-365X(77)90146-7
[10]	A. V. Kostochka, An analogue of Shannon's estimate for complete colorings, Metody Diskret. Analiz, in Russian, 30 (1977), 13–22.
[11]	A. V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math., 162 (1996), 199–214. https://doi.org/10.1016/0012-365X(95)00286-6 doi: 10.1016/0012-365X(95)00286-6
[12]	L. Kowalik, J. S. Sereni, R. Škrekovski, Total colouring of plane graphs with maximum degree nine, SIAM J. Discrete Math., 4 (2008), 1462–1479. https://doi.org/10.1137/070688389 doi: 10.1137/070688389
[13]	B. Mohar, C. Thomassen, Graphs on Surfaces, New York: Springer, 2001. https://doi.org/10.1007/978-1-4614-6971-1
[14]	D. P. Sanders, Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory, 31 (1999), 67–73. https://doi.org/10.1002/(SICI)1097-0118(199901)30:1<67::AID-JGT7>3.0.CO;2-M doi: 10.1002/(SICI)1097-0118(199901)30:1<67::AID-JGT7>3.0.CO;2-M
[15]	V. G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk, in Russian, 23 (1968), 117–134. https://doi.org/10.1070/rm1968v023n06abeh001252
[16]	W. Wang, Total chromatic number of planar graphs with maximum degree ten, J. Graph Theory, 54 (2014), 91–102. https://doi.org/10.1002/jgt.20195 doi: 10.1002/jgt.20195
[17]	H. Wang, B. Liu, J. Wu, Total coloring of graphs embedded in surfaces of nonnegative Euler characteristic, Sci. China Math., 57 (2014), 211–220. https://doi.org/10.1007/s11425-013-4576-2 doi: 10.1007/s11425-013-4576-2

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)