Linear Arboricity And Linear 2-arboricity Of Some Special Classes Of Graphs

A linear forest is a graph in which each connected component is a path,a linear k-forest is a graph in which each connected component is a path with length at most k.The concept of the linear arboricity of graph G was proposed by Harary in 1970,it is the minimum number t such that G can decompose into t linear forests,denoted by la(G).In 1980,Akiyama,Exoo and Harary conjectured:for any r-regular graph G,la(G)?r+1/2?.This is equivalent to the famous conjecture(LAC):for any simple graph G,??(G)/2??la(G)???(G)+1/2?.In 1982,Habib and Peroche further proposed the concept of linear k-arboricity,it is the minimum number t such that G can decom-pose into t linear k-forests,denoted by lak(G).They conjectured that for a simple graph G on n vertices(k>2),Prticularly,for k= 2,it is the linear 2-arboricity,denoted by la2(G).In this thesis,we mainly study the linear arboricity and linear 2-arboricity of some special classes of graphs.We also give some new proofs for some existing results.This thesis is organized as follows:In Chapter 1,we first introduce some notations and terms that will be used in this thesis;then we introduce the background and the recent developments of the concerned problems;the main results of this thesis are also stated in this chapter.In Chapter 2,we mainly study the linear arboricity of graphs.We give some results about the linear arboricity of a pseudotree.Inspired by the method in the proof of the NDT conjecture,we give some new proofs for the linear arboricity of 3-regular graphs and 4-regular graphs.In Chapter 3,we mainly study the linear 2-arboricity of graphs.First,we give the linear 2-arboricity of a pseudotree by finding a proper(t,2)-linear coloring.Next,we use the method of charge-discharge to study the structural properties of some special planar graphs and define the class of(k,1)-graphs.Finally,we obtain the linear 2-arboricity of the class of(k,1)-graphs and some other special classes of planar graphs.In Chapter 4,we summarize some further research work in these fields.