The Arboricity Problem Of Several Types Of Special Graphs

The coloring theory of the graph was originally derived from the "four-color conjecture" problem.After that,the coloring theory was continuously developed by people,and then vertex coloring,edge coloring and total coloring were extend.Among them,we mainly study edge coloring in this article.Specifically,the linear arboricity of planar graphs,the linear arboricity of graphs embedded in a surface of non-negative Euler characteristic,and the vertex arboricity of planar graphs.The graphs studied in this paper are all limited,simple and undirected graphs.The linear arboricity of graphs was originally defined by Harary in 1970.That is,the graph can be divided into the minimum number of linear forests,where the linear forest is the union of disjoint roads,and denoted by la(G).Later,through people's constant exploration,Akiyama,Exoo and Harary proposed a linear arboricity conjecture,that is,for any graph G,[?(G)/2]?la(G)?[?(G)+1/2],the ?(G)represents the maximum degree of the vertices of the graph G.The vertex arboricity of graphs was originally defined by chartrand in 1968,that is,the graph can be divided into the minimum number of forests,where the forest is the union of the trees without circles,and denoted by va(G).They have proved that for any planar graph,the va(G)?[1+?(G)/2],and for any planar graph,the va(G)?3.In chapter 1,we mainly introduce the development process of graph theory,as well as the definitions,symbols and terminology involved in this article.In chapter 2,we mainly studied the planar graphs with maximum degree A(G)?7,and discussed the linear arboricity of planar graphs without adjacent chordal i,j?{5,6,7}-cycles,then proved that its linear arboricity is[?(G)/2].In chapter 3,we mainly studied linear arboricity of graph which can be embeded in a surface of nonnegative Euler characteristic with maximum ?(G)?7,and discussed the linear arboricity of planar graphs without adjacent chordal 6-cycles,andproved that its linear arboricity(?(G)/2).In chapter 4,we studied the vertex arboricity of planar graphs that does not contain 5-cycles intersecting with 6-cycles,then proved that the vertex arboricity is satisfied va(G)?2.Finally,we have summarized this article and made an outlook on the vertex arboricity problem of the graph.