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)...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).展开更多
A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G suc...A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if 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 L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).展开更多
A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors.A graph G is acyclically k-choosable if for any list assignment L={L(v):v∈V(G)}with|L(v)|≥k for all v∈V(G),there exists a pro...A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors.A graph G is acyclically k-choosable if for any list assignment L={L(v):v∈V(G)}with|L(v)|≥k for all v∈V(G),there exists a proper acyclic vertex coloringφof G such thatφ(v)∈L(v)for all v∈V(G).In this paper,we prove that if G is a planar graph and contains no 5-cycles and no adjacent 4-cycles,then G is acyclically 6-choosable.展开更多
基金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).
基金supported by National Natural Science Foundation of China (Grant Nos. 11071223 and 11101377)Natural Science Foundation of Zhejiang Province,China (Gran No. Z6090150)+1 种基金Zhejiang Innovation Project (Grant No. T200905)Zhejiang Normal University Innovation Team Program
文摘A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if 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 L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).
基金Supported by Guangdong Province Basic and Applied Basic Research Foundation and Joint Foundation Project(Grant No.2019A1515110324)Natural Science Foundation of Guangdong province(Grant No.2019A1515011031)University Characteristic Innovation Project of Guangdong province(Grant No.2019KTSCX092)。
文摘A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors.A graph G is acyclically k-choosable if for any list assignment L={L(v):v∈V(G)}with|L(v)|≥k for all v∈V(G),there exists a proper acyclic vertex coloringφof G such thatφ(v)∈L(v)for all v∈V(G).In this paper,we prove that if G is a planar graph and contains no 5-cycles and no adjacent 4-cycles,then G is acyclically 6-choosable.
