|
|
关于图论课程教学中对染色问题的研究
|
Abstract:
图论起源于著名的哥尼斯堡七桥问题，是离散数学的重要分支。它在计算科学、社会科学和自然科学等多个领域都有广泛应用。本文主要研究广义Petersen图的非正常点染色问题，构造满足条件的染色方式。旨在帮助学生更好地理解图论基本概念，掌握图论中的基本技巧方法，从而培养学生科学解决问题的能力。
Graph theory, which originated from the famous Seven Bridges problem, is an important branch of discrete mathematics. It has extensive applications in many fields such as computing science, social science and natural science. In this paper, we mainly study improper coloring of generalized Petersen graphs and construct a coloring with certain requirement. It aims to help students under-stand the basic concepts and skills in graph theory, so as to guide student to develop the ability of solving scientific problems.
| [1] | Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable, Part II. Reducibility. Illinois Journal of Mathe-matics, 21, 491-567. https://doi.org/10.1215/ijm/1256049012 |
| [2] | Lin, Q.Z., Hou, J.F. and Liu, Y. (2012) Acyclic Edge Coloring of Graphs with Large Girths. Science China Mathematics, 55, 2593-2600. https://doi.org/10.1007/s11425-012-4442-7 |
| [3] | Yang, F. and Wu, J.L. (2022) The Total Coloring of K5-Minor-Free Graphs. European Journal of Combinatorics, 102, 103510. https://doi.org/10.1016/j.ejc.2022.103510 |
| [4] | 吴狄, 许宝刚, 许怡安. 围长 且无长奇洞图的染色问题[J]. 中国科学, 2023, 53(1): 103-120. |
| [5] | Andrews, J. and Jacobson, M. (1985) On a Generalization of Chromatic Number. Congressus Number, 47, 33-48. |
| [6] | Borodin, O.V. and Kostochka, A.V. (2014) Defective 2-Coloring of Sparse Graph. Journal of Combinatorial Theory, Series B, 104, 72-80. https://doi.org/10.1016/j.jctb.2013.10.002 |
| [7] | Borodin, O.V., Kostochka, A. and Yancey, M. (2013) On 1-Improper 2-Coloring of Sparse Graphs. Discrete Mathematics, 313, 2638-2649. https://doi.org/10.1016/j.disc.2013.07.014 |
| [8] | Choi, I. and Raspaud, A. (2015) Planar Graphs with Girth at Least 5 Are (3,5)-Colorable. Discrete Mathematics, 338, 661-667. https://doi.org/10.1016/j.disc.2014.11.012 |
| [9] | Chu, Y.N., Sun, L. and Yue, J. (2019) Note on Improper Coloring of 1-Planar Graphs. Czechoslovak Mathematical Journal, 69, 955-968. https://doi.org/10.21136/CMJ.2019.0558-17 |
| [10] | Li, X.W., Liu, J. and Lv, J.-B. (2022) Every Planar Graph with Girth at Least 5 Is (1,9)-Colorable. Discrete Mathematics, 345, 112818. https://doi.org/10.1016/j.disc.2022.112818 |
| [11] | Bondy, J.A.and Murty, U.S.R. (2008) Graph Theory. Springer, Berlin. |
| [12] | 林育青. 广义Petersen图 的着色[J]. 山西师范大学学报(自然科学版), 2010, 24(4): 8-11. |
