The Linear Vertex-arboricity Of Graphs And Related Problems

Let G be a finite and simple graph.For a graph G,we use V(G),E(G)and F(G)(or V,E and F)to denote its vertex set,edge set and face set,respectively.Let g(G)denote the girth of G which is the length of the shortest cycle in G.The vertex-arboricity of a graph G is the minimum number of subsets into which the set of vertices of G can be partitioned so that each subset induces a forest.The linear vertex-arboricity of a graph G is the minimum number of subsets into which the set of vertices of G can be partitioned so that each subset induces a linear forest.Let G1,...,Gn be n classes of graphs.Call a vertex partition of G a(G1,...,Gn)-partition if V(G)can be partitioned into n sets V1,...,Vn such that for each 1≤i≤n,the subgraph G[Vi]belongs to Gi.For simplicity,F,I,Δd,Fd and F2 denote the class of forests,the class of independent sets,the class of graphs with maximum degree d,the class of forests with maximum degree d,and the class of linear forests,respectively.The vertex-arboricity of a graph was first introduced by Chartrand,Kronk and Wall in 1968,and they proved the vertex-arboricity of a planar graph is at most 3.In 1979,Garey and Johnson proved that deciding the vertex-arboricity of any graph was NP-hard.In 1990,Poh proved the linear vertex-arboricity of a planar graph is also at most 3.Therefore,people began to consider the sufficient conditions which the linear vertex-arboricity of a planar graph is 2.In 2006,Chappell,Gimbel and Hartman proved the linear vertex-arboricity of a planar graph with girth 6 is at most 2.Besides,they constructed a planar graph with girth 4 and the linear vertex-arboricity of the graph is 3.Thus,we consider whether the linear vertex-arboricity of a planar graph with girth 5 is at most 2,i.e.admits an(F2,F2)-partition.The framework is shown as follows:In Chapter 1,we introduce some definitions and a brief survey of vertex-arboricity,linear vertex-arboricity and vertex partition.In 1998,Wu proved that the linear vertex-arboricity of the Halin Graph is at most 2.In Chapter 2,we improve the result and prove the following result:(1)Each Halin Graph admits vla(G)≤2,and the length of every path is at most max{[Δ-2/2],3}.In Chapter 3,Chapter 4 and Chapter 5,we make use of contradiction to show the planar graph with g(G)≥5 and without short adjacent(or intersect)cycles has an(Fi,Fj)-partition for some 2≤i,j≤5.The main methods are the coloring extension and the classical discharging.More precisely,we shall prove the following three results:(2)Every planar graph with girth 5 and without intersecting 5-cycles admits an(F2,F5)-partition.(3)Every planar graph with girth 5 and 5-cycles are not adjacent to 6--cycles admits an(F2,F4)-partition.(4)Every planar graph with girth 5 and without adjacent 5-cycles admits an(F3,F3)-partition.