含两个交叉的图的弱退化度
Weak Degeneracy of Graphs with Two Crossings
摘要: 图的弱退化度是由Bernshteyn和Lee提出的一个新的定义,是图的退化度的变形。 根据定义可知,每个d-退化的图也是d-弱退化的。 另一方面,如果G是d-弱退化的,那么χ(G) ≤ χl(G) ≤ χDP (G) ≤ d + 1。 因此,研究一些特殊图类的弱退化度有利于我们更好地深刻了解图的性质和特征。含有交叉的图是一类比平面图范围更大的图类。2011 年,Dvoˇr´ak 等人证明了含有至多两个交叉的图是5-可选的。 2018年,胡建章证明了含有至多一个交叉的图是5-在线可选的。2021年,李旭田和朱绪鼎证明了含有至多两个交叉的图是DP-5-可染的。在这篇论文中,证明了至多含 有2个交叉的图是4-弱退化的。
Abstract: Weak degeneracy of graphs is a new definition proposed by Bernshteyn and Lee. It is the variation of the degeneracy of graphs. By definition, every d-degenerate graph is also weakly d-degenerate. On the other hand, if G is weakly d-degenerate, then χ(G) ≤ χl(G) ≤ χDP (G) ≤ d + 1. So studying weak degeneracy of some special graph classes is beneficial for us to better understand the properties and features of graphs. Graphs with crossings are a class of graphs with a larger scope than planar graphs. In 2011, Dvoˇr´ak et al. proved that every graph with at most two crossings is 5- choosable. In 2018, Jianzhang Hu proved that every graph with at most one crossing is 5-paintable. In 2021, Xu’er Li and Xuding Zhu proved that every graph with at most two crossings are DP-5-colorable. In this paper, we prove that every graph with at most two crossings is weakly 4-degenerate.
参考文献
[1] |
Erdo˝s, P., Rubin, A.L. and Taylor, H. (1979) Choosability in Graphs. Congressus Numeran- tium, 26, 125-127. |
[2] |
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, Series B, 129, 38-54. https://doi.org/10.1016/j.jctb.2017.09.001 |
[3] |
Bernshteyn, A. and Kostochka, A. (2018) On Differences between DP-Coloring and List Col- oring. Siberian Advances in Mathematics, 21, 61-71. |
[4] |
Bernshteyn, A. and Lee, E. (2021) Weak Degeneracy of Graphs. arXiv:2111.05908 |
[5] |
Thomassen, C. (1994) Every Planar Graph Is 5-Choosable. Journal of Combinatorial Theory, Series B, 62, 190-191. https://doi.org/10.1006/jctb.1994.1062 |
[6] |
丁萧萧. 平面图l不含K5-子式图的弱退化度[J]. 应用数学进展, 2022, 11(7): 4760-4773. https://doi.org/10.12677/AAM.2022.117501 |
[7] |
Wang, T. (2023) Weak Degeneracy of Planar Graphs without 4- and 6-Cycles. arXiv: 2303.13267. |
[8] |
Han, M., Wang, T., Wu, J., Zhou, H. and Zhu, X. (2023) Weak Degeneracy of Planar Graphs and Locally Planar graphs. arXiv: 2303.07901 |
[9] |
Dvoˇr´ak, Z., Lidicky´, B. and Sˇkrekovski, R. (2011) Graphs with Two Crossings Are 5-Choosable. SIAM Journal on Discrete Mathematics, 25, 1746-1753. https://doi.org/10.1137/11082703X |
[10] |
胡建章. 含有交叉数的图的在线列表染色[J]. 运筹与模糊学, 2018, 8(2): 45-53. |
[11] |
李旭哥, 朱绪鼎. 含2个交叉的图是5-DP-可染的[J]. 浙江师范大学学报(白然科学版), 2021, 44(3): 252-258. |