Speaker：Min Chen（Zhejiang Normal University）

Time：2021-07-13 15:00

Location：Conference Room 686 at the 6th floor of Shuli Building at Haiyun Campus

Abstract:

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.