在一些充分条件下的不含4圈和7圈的平面图是2-弱退化的
Every Planar Graph with Some Sufficient Conditions but without 4- and 7-Cycles Is Weakly 2-Degenerate
DOI: 10.12677/AAM.2023.1210432, PDF,   
作者: 卢宏锴：浙江师范大学，数学科学学院，浙江 金华
关键词: 平面图；退化；弱退化；3-DP-可染；Planar Graph； Degenerate； Weakly-Degenerate； 3-DP-Colorble
摘要: 如果一个图G的每个子图中有一个点v，它的度数最多为k，那么我们称图G为k-退化的。k-弱退化图是k-退化图的推广。在这篇文章中，我们证明了不含4圈，7圈和特殊圈的平面图是2-弱退化的， 同时也是3-DP-可染的。由此得到结论：每个不含4圈，k圈，7圈和9圈的平面图是2-弱退化的以及3-DP-可染的，这里k ∈ {5, 6}。
Abstract: A graph G is k-degenerate if its every subgraph contains a vertex of degree at most k. Weakly k-degenerate graphs are a generalization of k-degenerate graphs. In this paper, we prove that every planar graph without 4, 7-cycles and some special cycles is weakly 2-degenerate. Consequently, it is 3-DP-colorable. As corollaries, every planar graph without 4-, k-, 7- and 9-cycles is weakly 2-degenerate and 3-DP-colorable, where k ∈ {5, 6}.
文章引用：卢宏锴. 在一些充分条件下的不含4圈和7圈的平面图是2-弱退化的[J]. 应用数学进展, 2023, 12(10): 4392-4402. https://doi.org/10.12677/AAM.2023.1210432

参考文献

[1] Dvoˇr´ak, Z. and Postle, L. (2018) Correspondence Coloring and Its Application to List-Coloring Planar Graphs without Cycles of Lengths 4 to 8. Journal of Combinatorial Theory, 129, 35-54. [Google Scholar] [CrossRef] 
[2] Wang, W. and Lih, K. (2002) Choosability and Edge Choosability of Planar Graphs without Five Cycles. Applied Mathematics Letters, 15, 561-565. [Google Scholar] [CrossRef] 
[3] Fijavˇz, G., Juvan, M., Mohar, B., Sˇkrekovsi, R. (2002) Planar Graphs without Cycles of Specific Lengths. European Journal of Combinatorics, 23, 377-388. [Google Scholar] [CrossRef] 
[4] Liu, R., Li, X., Nakprasit, K., Sittitrai, P. and Yu, G. (2020) DP-4-Colorability of Planar Graphs without Adjacent Cycles of Given Length. Discrete Applied Mathematics, 277, 245- 251. [Google Scholar] [CrossRef] 
[5] Sittitrai, P. and Nakprasit, K. (2021) Sufficient Conditions for Planar Graphs without 4-Cycles and 5-Cycles to Be 2-Degenerate. Discrete Mathematics, 344, Article 112564. [Google Scholar] [CrossRef] 
[6] Jumnongnit, P. and Pimpasalee, W. (2021) Planar Graphs without Specific Cycles Are 2- Degenerate. Discrete Mathematics, 344, Article 112488. [Google Scholar] [CrossRef] 
[7] Bernshteyn, A. and Lee, E. (2023) Weak Degeneracy of Graphs. Journal of Graph Theory, 103, 607-634. [Google Scholar] [CrossRef] 
[8] Han, M., Wang, T., Wu, J., Zhou, H. and Zhu, X. (2023) Weak Degeneracy of Planar Graphs and Locally Planar Graphs. arXiv:2303.07901v1.
[9] Wang, T. (2023) Weak Degeneracy of Planar Graphs without 4- and 6-Cycles. Discrete Applied Mathematics, 334, 110-118. [Google Scholar] [CrossRef] 

为你推荐