Linear 2-arboricity Of Graphs

The linear k-arboricity lak(G)of a graph G is the least integer m such that G can be partitioned into m edge-disjoint forests,whose component trees are paths of length at most k.Extremely,la1(G)is the edge chromatic number of G;lak(G)corresponds to the linear arboricity la(G)of G.In 1970,Harary introduced the linear arboricity of graphs.Akiyama,Exoo,and Harary(1980)proposed a conjecture that if G is a regular graph,then la(G)= ?(?(G)+ 1)/2?.Since la(G)? ??(G)/2? for any graph G,the conjecture is equivalent to the outstanding Linear Arboricity Conjecture(LAC):for any graph G,??(G)/2? ?1a(G)??(?(G)+ 1)/2?.In 1982,Habib and Peroche introduced the definition of linear k-arboricity and conjectured:Let G be a graph with'n vertices,and k ? 1 be a positive integer,thenIn this thesis,we study the linear 2-arboricity of planar graphs,toroidal graphs and some sparse graphs.The thesis consists of five Chapters.In Chapter 1,we introduce some basic conceptions,notations and technical terms used in the thesis,give a detailed survey in related topic and state the main results obtained in this thesis.Meanwhile,we introduce some lemmas on properties of linear 2-arboricity.In Chapter 2,we establish two edge-partition theorems of planar graphs,which will play an important role in the proofs of main results in the rest chapters.In Chapter 3,we consider the linear 2-arboricity of toroidal graphs and show that for any toroidal graph G,(1)la2(G)???(G)+1/2?+ 7;(2)if G doesn't contain some k-cycle,where k ? {3,4,5},then la2(G)???(G)+1/2?+4.In Chapter 4,we study the linear 2-arboricity of 2-degenarate graphs,and of sparse graphs with small maximum average degree.It is showed that:(1)if G is a 2-degenarate graph,then la2(G)???(G)/2? + 2;(2)if G is a graph with mad(G)<4,then la2(G)???(G)+1/2? 4;(3)if mad(G)<7/2,then la2(G)???(G)+1/2?+ 3;(4)if mad(G)<5,then la2(G)???(G)+1/2? + 10.In Chapter 5,we investigate the linear 2-arboricity of planar graphs with large maximum degree.We show that:if G is a planar graph with ?(G)? 9,then la2(G)??(G)-1.