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.