Acyclic Choosability of Graphs with Bounded Degree

• 作者: Juan WANG Lian Ying MIAO Jin Bo LI Yun Long LIU
• 来源期刊: 数学学报（英文版）
• 年，卷（期）: 2022,（3）
• 页码范围: 560-570
• 页数: 11页
• 语种: 英文

摘要

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