Vertex Forest Partitioning Of Graphs

Let G be a finite,simple and undirected graph.We use V(G),E(G),?(G)and?(G)to denote its vertex set,edge set,the maximum degree,and the minimum degree,respectively.Denote m classes of graph by g1,g2,…,gm.If we can partition all vertices of G into subsets V1,V2,…,Vm such that for each 1 ?i?m,G[Vi]is a forest,then we call such a partition is a(g1,g2,…,gm)-partition of G.For convenience,we use F,L and Td to denote the class of forests,the class of independent sets and the class of forests with maximum degree k,respectively.The vertex-arboricity va(G)of a graph G is the minimum number of subsets into which the vertex set V(G)can be partitioned so that each subset induces a forset.It was first introduced in 1968 by Chartrand,Kronk and Wall.They proved that va(G)?[1+?(G)/2].for every graph G and va(G)?3 for every planar graph G.In 2008,Raspaud and Wang firstly gave an equivalent definition to the vertex-arboricity in terms of the coloring version.A forest k-coloring of a graph G is a mapping? from V(G)to a[k]color set such that each color class induces an acyclic subgraph.The vertex-arboricity va(G)of G is the smallest integer k such that there exists a forest k-coloring of G.A graph G is called to be L-forested-colorable if for any color list L={L(v)| v ?V(G)},one can choose an element(color)for each vertex v from its list L(v)so that the subgraph induced by every color class is a forest.The list vertex-arboricity val(G)is the minimum number of integer k such that G is L-forested-colorable with |L(v)|? k for each v ? V(G).In this master thesis,we study the vertex forest partition of toroidal graphs.The framework is shown as follows:In Chaper 1,we will first introduce some basic definition and notations.Next we will summarize the current research results in this related fields and present our main results.In Chapter 2,we study the list vertex-arboricity of toroidal graphs and prove that every toroidal graph G containing neither K5-nor 6-cycles satisfies val(G)?2.This is best possible in the sense that forbidding only one of two structures,say a K5-or a 6-cycle,cannot guarantee its vertex-arboricity being at most 2.In Chapter 3 and Chapter 4,we consider the forested partition with restricted max-imum degree.More precisely,we prove that for each i? {6,7},every toroidal graph without 4-cycles and i-cycles admits an(F,F3)-partition.