Planar graphs without {4,8,9}-cycles are acyclically 4-choosability

：陈敏
：2021-07-13 15:00
：厦大海韵园数理大楼6楼686

报告人：陈敏（浙江师范大学）

时  间：7月13日下午15:00

地  点：厦大海韵园数理大楼686会议室

内容摘要:

Let G = (V,E) be a graph. A proper vertex coloring of G is acyclic if G contains no bicolored cycle. Namely, every cycle of G must be colored with at least three colors. G is acyclically L-colorable if for a given list assignment L = {L(v) : v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L-colorable for any list assignment with |L(v)| ≥ k for all v ∈V, then G is acyclically k-choosable. This concept was introduced by Grünbaum in 1973.

It is known that for any two integers i and j such that {i,j} ⊂ {5,6,7,8,9} and {i,j}≠{8,9},every planar graph without {4,i,j}-cycles is acyclically 4-choosable. In this talk, we shall complete the last remaining case by proving that every planar graph without {4,8,9}-cycles is acyclically 4-choosable.

个人简介：

陈敏，浙江师大数学与计算机科学学院教授、博士生导师，副院长。2010年法国波尔多第一大学获博士学位。浙江省高校中青年学科带头人。主要研究方向为图的染色理论。迄今在包括J. Combin. Theory Ser. B、European J. Combin.、J. Graph Theory等重要国际学术刊物在内发表论文50多篇。主持国家自然科学基金项目3项，现为国际组合优化期刊JOCO编委。

 

联系人：金贤安