The Point Arboricity Of The Graph And The List Point Arboricity

The vertex-arborictity va(G)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.A forest k-coloring of a graph G is mapping ?:V(G)?{1,2,...,k},such that each color class induces a forest.The vertex-arboricity is also the least integer k such that G has a forest k-coloring.Suppose that L is the list assignment of V(G).If G has a forest coloring such that?(v)?L(v)for each v?V(G),then we say that G is forest L-colorable.If for any list assignment L with |L(v)|?k,G is forest L-colorable,then G is called forest k-choosable.The list vertex-arboricity valist(G)is the least integer k such that G is forest k-choosable.In 1968,the vertex-arboricity of a graph was first introduced by Chartrand,Kronk and Wall.At the same time,they proved that va(G)?[?+1/2],and the vertex-arboricity of planar graphs is at most 3.In 2008,Raspaud and Wang proved that every planar graph G without k-cycles for some fixed k?{3,4,5,6} has va(G)<2.They asked the following question:what is the maximum integer p for all k?{3,4,5,...,?},a planar graph G with no k-cycles has va(G)? 2.In 2012,Huang,Shiu and Wang extended it to 7 by showing that va(G)<2 if G is a planar graph with no 7-cycles.In 2012,Chen,Raspaud and Wang proced a conjecture by Raspaud and Wang which said that va(G)<2 if G is a planar graph without intersecting triangles.A natural question is:Does the planar graph G without intersecting k-cycles,k?{4,5,6,7},have va(G)<2?In 2018,Cai,Wu and Sun proved that if G is a planar graph without intersecting 5-cycles,then va(G)?2.In 2009,Borodin and Ivanova proved that if G is a planar graph without 3-cycles adjacent to 4-cycles,then valist(G)?2.For the toroidal graph,is the above result valid?In 2016,Chen,Huang and Wang proved that if G is a toroidal graph without 3-cycles adjacent to 4-cycles,then vlist(G)?2.In 2014,Zhang proved that if G is a toroidal graph without 5-cycles,then valist(G)?2.In 2015,Huang,Chen,Wang proved that if G is a toroidal graph without 3-cycles adjacent to 5-cycles,then valist(G)?2.In 2016,Zhang proved that every toroidal graph G has va(G)<2,when G contains neither 7-cycles nor adjacent,triangular 4-cycles.In this master thesis,we mainly study the vertex-arboricity and list vertex-axboricity problems of some special graphs,say toroidal graphs and planar graphs.The thesis consists of three chapters.In Chapter 1,we introduce the basic concepts and the results of vertex-arboricity and list vertex-arboricity.At the same time,we introduce the main results of this paper.In Chapter 2,we study the vertex-arboricity of planar graphs and get the following two results:(1)Every planar graph G without 3-cycles adjacent to 6-cycles has va(G)?2.(2)Let G be a planar graph.If every vertex of G is not simultaneous incident with 3-,4-,5-and 6-cycles,then va(G)?2.In Chapter 3,we study the list vertex-arboricity of toroidal graph by showing that:Let G be a toroidal graph such that every 5-cycle is not simultaneous adjacent to 3-cycles and 4-cycles.Then valist(G)?2.