The Linear Arboricity And Linear 2-Arboricity Of Some Special Graphs

Graph coloring problem originated from the map problem,the famous four color con-jecture:every map can be coloured with four colours in such a way that adjacent countries are coloured differently.Mathematician Hector Wood proved the five-color theorem,every nap can be coloured with five or fewer colours.Whereafter,about the four color conjecture prove that there are many versions,but all the process are very complicated.After four years of hard work,American mathematicians Appel and Haken completed the proof of the four color conjecture with a computer,until June 1976.Then the four color conjecture renamed four color theorem.But,many mathematicians do not satisfied with the computer of the existing achievements,they prefer to get a simple proof method which can be written.But.this idea has yet to achieve.Graph coloring problem as an important branch of the edge coloring of graphs,has very practical application in our actual life.The linear arboricity and the linear k-arboricity of a graph G as a class of the edge coloring of graph,has important research significance in the decomposition of graph.Given a graph G,if G can be partitioned into m edge-disjoint linear forests,then we call the minimum integer m the linear arboricity of G,denoted by la(G);if G can be partitioned into m edge-disjoint linear k-forests,then we call the minimum integer m the linear k-arboricity of G,denoted by lak(G).Recently,the arboricity of a graph has a wide range of research,but the study of linear k-arboricity of a graph G is relatively less.This article study the linear arboricity and linear k-arboricity(when k = 2)of a graph.The main content of thesis is divided into the following four parts:In chapter 1,we introduce some basic concepts and symbols used in the thesis the emergence and development of the linear arboricity and linear k-arboricitv of graphs,and the main results of this paper are presented.In chapter 2,we study the linear arboricity of planar graphs which has no 3-fans.First,by using the theory of graph coloring study the structure properties of k-deletion-minimal.and then use discharging method to prove the linear arboricity of every planar graph without 3-fans satisfied la(G)≤ 4,if △(G)≤ 8.In chapter 3,we study the linear 2-arboricity of some graphs has property Pk By studying the edge-partitions of graphs obtain related structure lemmas,and then on the basis of the existing conclusions complete the main conclusions of this chapter.In the end,we use the results to improve the upper bound of some planar’s linear 2-arboricity.In chapter 4,conclusion part.The detailed instructions and prospect about some prob-lems in the thesis that has a further research space and sense.