Linear Arboricity And Light Structure Of Graphs

In this Ph.D.dissertation,we study the linear arboricity and the light structure of graphs.The linear arboricity la(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.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.Assume that xy ? E(G).If d_G(x)+d_G(y)?M,then we say xy is an M-light edge;If d_G(x)? a and d_G(y)?b,then we say xy is a(a,b)-edge;If d_G(x)?a and d_G(y)?b,then we say xy is a(a,b)-edge.In 1970,Harary introduced the linear arboricity of a graph.In 1980,Akiyama,Exoo and Harary raised the linear arboricity conjecture(LAC):For any graph G,(?)(?).And,they showed that the LAC is true for complete graphs,complete bipartite graphs,trees and the graphs with ?=3,4.In 1984,Enomoto and Peroche proved that LAC holds for graphs with ?=5,6,8.Wu et al.showed that LAC holds for the class of planar graphs.In 1982,Habib and Peroche introduced the linear k-arboricity of a graph.In 2003,Lih,Tong and Wang proved that every planar graph G has(?).This result later was improved to that(?)by Wang et al.In 2018,Wang et al.showed that every toroidal graph G has(?).In 1955,Kotzig proved that every 3-connected planar graph G contains a(3,10-)-edge,or a(4,7-)-edge,or a(5,6-)-edge,and all results are best possible.In 2007,Fabrici and Madaras proved that every 3-connected 1-planar graph contains a(20-,20-)-edge.At the same time,they constructed a 1-planar graph with a(3,20)-edge.In this Ph.D.dissertation,we study the linear arboricity of 1-planar graphs and IC-planar graphs,the linear 2-arboricity of 1-planar graphs and torodial graphs,and the light structure of 1-planar graphs.The dissertation consists of four chapters as follows.In Chapter 1,we collect some concepts and notation used in the dissertation,give a detailed survey on the research progress of related areas,and state the main results obtained in the dissertation.In Chapter 2,we study the linear arboricity of 1-planar graphs and IC-planar graphs.Main results are follows:(1)If G is a 1-planar graph with ?? 13,then G satisfies LAC.(2)If G is a 1-planar graph with ??7,9,then G satisfies LAC.(3)If G is an IC-planar graph with ??7,then G satisfies LAC.In Chapter 3,we investigate the linear 2-arboricity of 1-planar graphs and torodial graphs,and confirm the following conclusions:(1)If G is a 1-planar graph,then(?).(2)If G is a torodial graph,then(?).In Chapter 4,we focus on the light structure of 1-planar graphs by establishing the following:(1)If G is a 1-planar graph with ?? 3,then G contains a(3,20-)-edge,or a(4,11-)-edge,or a(5,9-)-edge,or a(6,8-)-edge,or a(7,7)-edge.Moreover,the uppers bound 20,9,8,7 are best possible,and 11 is almost optimal.(2)If G is a 1-planar graph with ?? 2 and without 4-cycle,then G contains a(15-,15-)-edge.