Vertex Partition Problems Of Planar Graphs With Girth Restrictions

For each i ∈ {1,2,...,m},let Gi be a class of graphs.We say that a graph G admits a(G1,G2,...,Gm)-partition if V(G)can be partitioned into m subsets Vi,V2,...,Vm such that(1)for any i,j ∈ {1,2,...,m},Vi∩Vj=?;(2)V1∪V2∪…∪Vm=V(G);(3)G[Vi]is a graph in Gi.Let k be an integer.We use L,F,Ok,Pk and Tk to denote the class of edgeless graphs,the class of forests,the class of graphs whose components have order at most k,the class of graphs whose components are paths of order at most k and the class of graphs whose components are trees of order at most k.In this paper,we mainly study the vertex partition problems of planar graphs with girth restrictions.This thesis is organized as follows:In Chapter 1,we first introduce some notations and basic definitions in graph theory.Then we introduce the research background of partition of planar graphs.Finally,three main theorems of this paper are listed.In Chapter 2,Choi,Dross and Ochem proved that every planar graph with girth at least 9 admits an(L,O9)-partition.We add restrictions to this result and prove the theorem by using the discharging method:Every planar graph with girth at least 9 and without intersecting 9-cycles admits an(L,O6)-partition.In Chapter 3,we prove that every planar graph with girth at least 6 and i-cycle is not intersecting with j-cycle admits an(O2,O3)-partition,where i∈｛6,7,8} and j∈{6,7,8,9}.In Chapter 4,we prove that every planar graph with girth at least 5 and icycle is not intersecting with j-cycle admits a(T5,T5)-partition,where i∈｛5,6}and j ∈ {5,6,7,8,9}.In Chapter 5,we propose some problems for further researches.