含两个交叉的图的弱退化度

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.