We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Acyclic Choosability of Graphs with Bounded Degree.
- Authors
Wang, Juan; Miao, Lian Ying; Li, Jin Bo; Liu, Yun Long
- Abstract
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).
- Subjects
ACYCLIC model
- Publication
Acta Mathematica Sinica, 2022, Vol 38, Issue 3, p560
- ISSN
1439-8516
- Publication type
Article
- DOI
10.1007/s10114-022-0097-7