The vertex-arboricity a(G)of a graph G is the minimum number of colors required for a vertex coloring of G such that no cycle is monochromatic.The list vertex-arboricity al(G)is the list-coloring version of this conce...The vertex-arboricity a(G)of a graph G is the minimum number of colors required for a vertex coloring of G such that no cycle is monochromatic.The list vertex-arboricity al(G)is the list-coloring version of this concept.In this paper,we prove that every planar graph G without intersecting 5-cycles has al(G)≤2.This extends a result by Raspaud and Wang[On the vertex-arboricity of planar graphs,European J.Combin.29(2008),1064-1075]that every planar graph G without 5-cycles has a(G)≤2.展开更多
The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the follow...The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the following results have been obtained. For any graph G of order p,and the bounds are sharp; especially as an integer function, 5p+7 could not be decreased. Furthermore, Nordhaus-Gaddum Theorem for arboricity has also been got.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11971437,11771402)the Natural Science Foundation of Zhejiang Province(No.LY19A010015).
文摘The vertex-arboricity a(G)of a graph G is the minimum number of colors required for a vertex coloring of G such that no cycle is monochromatic.The list vertex-arboricity al(G)is the list-coloring version of this concept.In this paper,we prove that every planar graph G without intersecting 5-cycles has al(G)≤2.This extends a result by Raspaud and Wang[On the vertex-arboricity of planar graphs,European J.Combin.29(2008),1064-1075]that every planar graph G without 5-cycles has a(G)≤2.
文摘The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the following results have been obtained. For any graph G of order p,and the bounds are sharp; especially as an integer function, 5p+7 could not be decreased. Furthermore, Nordhaus-Gaddum Theorem for arboricity has also been got.
