Arc-weighted acyclic orientations and variations of degeneracy of graphs

发布时间：2023-12-26 作者：浏览次数：

Speaker:	朱绪鼎	DateTime:	2023年12月30日（周六）上午10:00-11:00
Brief Introduction to Speaker: 朱绪鼎：曾担任台湾中山大学西湾讲座教授，第三批国家入选者。作为图论与组合优化研究领域的著名专家，朱绪鼎在图的染色理论、结构分析、演算法等领域做出了杰出的贡献，取得一系列重大研究成果，特别是创新发展了图的圆染色理论，使得该方向已成为当前国内外研究的热点之一。朱绪鼎曾先后在国际重要学术刊物上发表SCI研究论文130余篇，论文被同行引用1000余次。2007年，在ISI公布的、有全球900多位数学家入选的世界数学家被引用次数排名中，位列第67名。现为浙江师范大学教授。		Place:	6号楼M213报告厅
Abstract:This talk introduces generalizations of the concept of acyclic orientations to arc-weighted orientations. These lead to variations of degeneracy of graphs, that provide better upper bounds for various colouring parameters, including the choice number, the DP-paint number and the AT-number of graphs. As a consequence, we conclude that planar graphs of girth 5 are 3-AT, which strengthens Thomassen's result that planar graphs of girth 5 are 3-choosable, and locally planar graphs are 5-AT, which strengthens a result of DeVos, Kawarabayashi and Mohar that locally planar graphs are 5-choosable. A variation of the degeneracy is used to study $k$-truncated-degree-choosability of graphs. We construct a 3-connected planar graph which is not 7-truncated-degree choosable, which answers an open question of Richter in negative, and show that that every 3-connected non-complete planar graph is $16$-truncated-degree-choosable. It is also shown that for any surface $\Sigma$, there is a...

上一条： Covering Graphs by Subgraphs
下一条： Infinite dimensional Lie algebras and symmetric functions