The Linear Arboricity Of 1-planar Graphs And Related Problems

Let G be a finite,undirected and simple graph.For a graph G,we use V(G)and E(G)(or V and E)to denote its vertex set and edge set,respectively.A linear forest is a forest in which each connected component is a path.A linear k-forest is a forest in which each connected component is a path of length at most k.An edge-partition of a graph G is a decomposition of G into subgraphs G1,G2,…,Gm such that E(G)=E(G1)?…?E(Gm)and E(Gi)? E(Gj)=(?)for i?j.The linear arboricity la(G)is the least integer m such that G can be edge-partitioned into m linear forests.The linear k-arboricity lak(G)is the least integer m such that G can be edge-partitioned into m linear k-forest.The linear arboricity of a graph was first introduced by Harary in 1970.In 1980,Akiyama,Exoo and Harary gave the following conjecture:For all ?(G)-regular graphs G,we have la(G)=[?(G)+1/2].Then,many scholars continue to study the linear arboricity problems and form the famous linear arboricity conjecture:For all simple graphs,we have[?(G)/2]?la(G)?[?(G)+1/2]By summarized the results of linear arboricity of planar graphs,we get that the linear arboricity conjecture holds for all simple planar graphs.In 2011,Zhang,Liu and Wu studied the structural properties of 1-planar graphs and proved that if G is a 1-planar graphs with ?(G)?33,then la(G)=[?/2],In 2013,Zhang and Liu showed that if G is an IC-planar graphs with ?(G)?17,then la(G)=[?/2].The linear k-arboricity of a graph was first introduced by Habib and Peroche in 1982.Jackson and Warmald studied the linear k-arboricity of graphs with ?(G)?3.Thomassen proved that the linear k-arboricity of graphs with ?(G)?3 is lak(G)?k where k?5.In 2003,Lih et al.studied the linear 2-arboricity problems of planar graphs and proved that la2(G)?[?(G)+1/2]+12 for planar graphs.Wang et al.studied the structural properties of toroidal graphs and proved that the linear 2-arboricity of a toroidal graph is at most[?(G)+1/2]+7.Liu et al.proved that the linear 2-arboricity of a 1-planar graph is la2(G)?[?(G)+1/2]+7.In this paper,we investigate the structural properties of 1-pianar graphs and IC-planar graphs,and improve the existing results of linear arboricity.The framework is shown as follows:In Chapter 1,we introduce the definitions of linear arboricity,survey the related results,and introduce the main results in this paper.In 2011,Zhang,Liu and Wu proved that if G is a 1-planar graphs with ??33,then the linear arboricity is[?/2].In Chapter 2,we improve this result and prove the following result:(1)If G is a 1-planar graph with ?(G)?25,then la(G)=[?(G)/2].In Chapter 3,we improve the result of Zhang and Liu for IC-planar graphs and prove the following result:(2)If G is an IC-planar graph with ?(G)?15,then la(G)=[?(G)/2].In Chapter 4 and Chapter 5,we find the construction of minimal counterexamples and use the method of discharging to prove the following two results:(3)If G is an IC-planar graph with ?(G)? 9 and without 4-cycles,then la(G)=[?(G)/2](4)If G is a toroidal graph without 5-cycles and without adjacent 4-cycles,then la2(G)?[?(G/2]+4.