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

Weak Degeneracy of Graphs with Two Crossings

在线阅读下载全文

作  者:王程 

机构地区:[1]浙江师范大学,数学科学学院,浙江 金华

出  处:《应用数学进展》2023年第8期3639-3650,共12页Advances in Applied Mathematics

摘  要:图的弱退化度是由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-弱退化的。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.

关 键 词:交叉数 退化 弱退化  

分 类 号:O15[理学—数学]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象