科学研究
学术报告
当前位置: 学院主页 > 科学研究 > 学术报告 > 正文

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...