最大度大于等于八的可嵌入图的全染色
Total Coloring of Embedded Graphs with Maximum Degree at Least Eight
DOI: 10.12677/PM.2021.118169, PDF,    科研立项经费支持
作者: 王丽婷*, 王慧娟#：青岛大学数学与统计学院，山东 青岛
关键词: 欧拉示性数；曲面；全染色；权转移方法；Euler Characteristic； Surface； Total Coloring； Discharging Method
摘要: 图的染色问题是图论中的一个重要研究方向，在计算机科学，组合优化和网络优化等方面有非常重要的应用，全然色是一种重要的染色。本文利用权值转移的方法证明了，如果G是最大度大于等于八的可嵌入到欧拉示性数非负曲面的图，且G中不包含相邻的4-圈，那么图G的全色数等于最大度加一。
Abstract: Graph coloring is an important research direction in graph theory. It has very important applica-tions in computer science, combination optimization and network optimization. Total coloring is an important type of coloring. In this paper, we use the discharging method to prove that if G is a graph of maximum degree that is equal or greater than eight, and it can be embedded into a nonnegative surface of Euler characteristic, and G does not contain adjacent 4-cycles, then the total chromatic number of G is equal to its maximum degree plus one.
文章引用：王丽婷, 王慧娟. 最大度大于等于八的可嵌入图的全染色[J]. 理论数学, 2021, 11(8): 1505-1510. https://doi.org/10.12677/PM.2021.118169

参考文献

[1] Bondy, J.A. and Murty, U.S.A. (1976) Graph Theory with Applications. MacaMillan, London, 1-197. [Google Scholar] [CrossRef] 
[2] Behzad, M. (1965) Graphs and Their Chromatic Numbers. Michigan State University, Michigan.
[3] Vizing, V.G. (1968) Some Unsolved Problems in Graph Theory. Uspekhi Matematicheskikh Nauk, 23, 117-134. [Google Scholar] [CrossRef] 
[4] Kostochka, A.V. (1996) The Total Chromatic Number of Any Multigraph with Maximum Degree Five Is at Most Seven. Discrete Mathematics, 162, 199-214. [Google Scholar] [CrossRef] 
[5] Zhao, Y. (1999) On the Total Coloring of Planar Graphs Embeddable in Surfaces. Narnia, 60, 333-341. [Google Scholar] [CrossRef] 
[6] Wang, H.J. and Liu, B. (2014) Total Coloring of Embedded Graphs with Maximum Degree at Least Seven. Theoretical Computer Science, 518, 1-7. [Google Scholar] [CrossRef] 
[7] 王颖. 嵌入到欧拉示性数非负曲面上的图的全染色[D]: [硕士学位论文]. 济南: 山东大学, 2014.
[8] Wang, B. and Wu, J.L. (2018) Total Coloring of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles. Discusions mathematicae Graph Theory, 38, 978-983. [Google Scholar] [CrossRef] 
[9] Borodin, O.V. (1989) On the Total Coloring of Planar Graphs. Journal für die reine und angewandte Mathematik, 394, 180-185. [Google Scholar] [CrossRef] 
[10] Hou, J.F. and Zhu, Y. (2008) Total Coloring of Planar Graphs without Small Cycles. Graphs and Combinatorics, 24, 91-100. [Google Scholar] [CrossRef] 
[11] Wang, W.F. (2007) Total Chromatic Number of Planar Graphs with Maximum Degree Ten. Graph Theory, 54, 91-102. [Google Scholar] [CrossRef] 
[12] Kowalik, L. and Sereni, J.S. (2008) Total Coloring of Plane Graphs with Maximum Degree Nine. Discrete Mathematics, 22, 1462-1479. [Google Scholar] [CrossRef] 
[13] 王慧娟. 可嵌入图的染色问题[D]: [博士学位论文]. 济南: 山东大学. 2015.

为你推荐