Linear Arboricity And Vertex Arboricity Of Graphs

In this thesis,we study the linear arboricity and the vertex arboricity of graphs and all graphs considered in this paper are finite simple graphs.The vertex-arboricity va(G)of a graph G was first introduced by Chartrand, Kronk and Wall.The concept of linear arboricity was introduced first by Harary in[12].Let la(G)and△(G)denote the linear arboricity and the maximum degree of a graph G.The fundamental question in the study of linear arboricity is a conjecture: For any graph G,[△(G)/2]≤la(G)≤[△(G)+1/2].In chapter 1,we introduce some basic notions used in this thesis,give a chief survey on this direction and main results in the thesis.In chapter 2,we first introduce the concept of the cubic graph G3 of a graph G:Let two vertices u,v,∈V(G),the distance between u and v,denoted by dG(u,v),is the length of the smallest path between u and v.The three cubed graph G3 of a graph G is the graph defined on V(G3)=V(G), E(G3)={uv:u,v∈V(G),u≠v,dG(u,v)≤3}. Let△denote the maximum degree of a graph G,Then the vertex arboricity of the graph G3 atisfies the inequation [△+1/2]≤va(G3)≤[△3-△2+△+1/2]Finally,Let Cn3 denote the three cubed graph of cycle Cn,We study the vertex arboricity of Cn3.In chapter 3,we study the linear arboricity of planar graphs.It is proved that Linear Arboricity Conjecture holds for planar graphs with△(G)=7 and without 3-cycles.