Acyclic Choosability of Graphs with Bounded Degree  

作　　者：Juan WANG Lian Ying MIAO Jin Bo LI Yun Long LIU 

机构地区：[1]School of Management,Qufu Normal University,Rizhao,276826,P.R.China [2]School of Mathematics,China University of Mining and Technology,Xuzhou,221116,P.R.China [3]College of Engineering,Qufu Normal University,Rizhao,276826,P.R.China

出　　处：《Acta Mathematica Sinica,English Series》2022年第3期560-570,共11页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant Nos.11771443 and 11601510);Shandong Province Natural Science Foundation(Grant No.ZR2017QF011)。

摘　　要：An acyclic colouring of a graph G is a proper vertex colouring such that every cycle uses at least three colours. For a list assignment L = {L(v)| v∈V(G)}, if there exists an acyclic colouringρ such that ρ(v)∈L(v) for each v∈V(G), then ρ is called an acyclic L-list colouring of G. If there exists an acyclic L-list colouring of G for any L with |L(v)|≥k for each v∈V(G), then G is called acyclically k-choosable. In this paper, we prove that every graph with maximum degree Δ≤7 is acyclically 13-choosable. This upper bound is first proposed. We also make a more compact proof of the result that every graph with maximum degree Δ≤3(resp., Δ≤4) is acyclically 4-choosable(resp., 5-choosable).

关 键 词：Acyclic choosability list colouring acyclic colouring maximum degree 

分 类 号：O157.5[理学—数学]