Vertex Decomposition Of Graphs

Let G be a finite and simple graph.For a graph G,we use V?G?and E?G?to denote its vertex set and edge set,respectively.Denote m classes by graphs G₁,...,G_m.Call a vertex partition of G a?G₁,...,G_m?-partition if V?G?can be partitioned into m sets V₁,...,V_msuch that for each 1?l?m,the subgraph G[V_l]belongs to G_l.For simplicity,we denote the class of forests,the class of independent sets,the class of graphs with maximum degree k,and the class of forests with maximum degree k by using notation F,I,?_kand F_k,respectively.The maximum average degree of G is defined to be mad?G?=max{?2|E?H?|?/?|V?H?|?:H?G}.Let g?G?denote the girth of G which is the length of a shortest cycle in G.If G is a connected planar graph,then mad?G?<?2g?G??/?g?G?-2?.In 2013,for any d₁and d₂,Montassier and Ochem constructed graphs with g?4 that do not admit any?d₁,d₂?-partition.So people mainly considered the(?_d1,?_d2)-partition problem of planar graphs with g?5.Later,concerning this problem,Havet and Sereni proved that graphs with g?5 admit a??₄,?₄?-partition,Choi and Raspaud proved that graphs with g?5 admit a??₃,?₅?-partition.Finally Borodin and Kostochka proved that graphs with g?5 admit a??₂,?₆?-partition.For the(?_d1,?_d2)-partition problem of planar graphs with g?6,in 2014,Borodin and Kostochka obtained that every graph G satisfying mad?G???16?/5 admits a??₁,?₄?-partition.This yields that every planar graph with girth g?6 admits a??₁,?₄?-partition.On the other hand,Borodin et al.proved that for every d,there exists a planar graph of girth 6 that admits no?I,?_d?-partition.So for planar graphs with girth g?7,it is significant to consider whether there exists an?I,?_k?-partition?or an?I,F_k?-partition?or not.On the other hand,recently,Borodin and Kostochka obtained that every graph G satisfying mad?G??8/3 admits an?I,?₂?-partition and every graph G satisfying mad?G???14?/5 admits an?I,?₄?-partition.As a corollary,we have that every planar graph with girth g?7 admits an?I,?₄?-partition and every planar graph with girth g?8 admits an?I,?₂?-partition.In fact,Montassier and Ochem proved that deciding if a planar graph of girth g?7 has an?I,?₂?-partition is NP-complete.Recently,Dross,Montassier and Pinlou considered?I,F_k?-partition problems of the same family of planar graphs.They showed that every planar graph with girth g?7 admits an?I,F₅?-partition and every planar graph with girth g?8 admits an?I,F₃?-partition.Basing on above research,in this master thesis,we shall investigate this problem.The framework is shown as follows:In Chapter 1,we first present some basic concepts,then introduce the current re-search status of related fields and the results of our thesis.In Chapter 2,Chapter 3 and Chapter 4,we shall make use of contradiction to show that the minimal counterexample cannot exist.The main methods are the coloring extension,potential function and the classical discharing method.More precisely,we will prove the following three results.?1?Planar graphs with girth a g?5 admit(F_d1,F_d2)-partition,where{d₁,d₂}?{{4,4},{3,5},{2,6}}.?2?Planar graphs with girth g?6 admit a?F₁,F₄?-partition.?3?For k?2,every graph G with mad?G??2+k/?k+1?admits an?I,F_k?-partition.It should be noted,the first result is a common strengthening of previous result in[10,24,31].?2?and?3?improved two results published in Journal of Combinatorial Theory,Series B.Besides,since there exists a planar graph with girth 6 that admits no?I,?_d?-partition,the class of F₁cannot be improved.