Some Research On Extremal Problems For Linear Forests

A linear forest is a forest consisting of vertex-disjoint paths.Specially,a path is a linear forest.Many problems in graph theory are developed from studying of paths,and then will be naturally extended to linear forests,forests and so on.In this paper,we will study with some extremal problems for linear forests,including the bipartite Turán numbers of linear forests,the anti-Ramsey numbers of linear forests and rainbow linear forests in edge-colored graphs.Particularly,all of those problems are closely related to the Turán problem.In the first chapter,we brief the research background and preliminary knowledge.Then we review the development of the Turán problem,bipartite Turán problem,and anti-Ramsey type problems for linear forests,and present our results of those problems.In the second chapter,we focus on the bipartite Turán problem for linear forests.Given a graph F and integers n,m,we call the maximum number of edges in an(m,n)bipartite graph which does not contain F as a subgraph bipartite Turán number,denote by ex(m,n;F).Based on the known research about bipartite Turán numbers for linear forests,we conduct further research on this problem.By using a result of Yuan and Zhang,we reduce the problem to a version with more conditions about the sum of degrees for pairs of vertices.Furthermore,by using a stability result for paths in bipartite graphs and other tools,we determine the bipartite Turán numbers of linear forests in F when n≥m and m is sufficiently large,and characterize the extremal graphs,where F includes all linear forests consisting of paths on at least four vertices,copies of path on three vertices,all linear forests consisting of paths on two or three vertices and all linear forests consisting of paths on two or at least four vertices.In the third chapter,we study the anti-Ramsey numbers of linear forests.For a fixed graph F and an integer n,the anti-Ramsey number AR(n,F),is the maximum number of colors in an edge-coloring of Kn which does not contain a rainbow copy of F.Fang,Gy?ri,Lu and Xiao determined the exact value of anti-Ramsey number of linear forests consisting of all odd paths,and characterized the extremal edge-colored complete graphs.We determine the exact value of anti-Ramsey numbers of linear forests when n is sufficiently large,and show the extremal edge-colored graphs.This answers the question of Fang,Gy?ri,Lu and Xiao.In the fourth chapter,we propose a problem based on the research on anti-Ramsey numbers of linear forests.We conjecture that for a fixed linear forest F and an integer n,if an edge-colored graph satisfies that the sum of the number of edges and the number of colors is larger than the sum of the number of edges of Kn and AR(n,F),then this edgecolored graph contains a rainbow copy of F.By combining the method of proving of anti-Ramsey numbers for paths and the method of our research on anti-Ramsey numbers of linear forests in the third chapter,we confirm our conjecture is right for any linear forest when n is sufficiently large.In the last chapter,we summarize the paper and look into the future research plan based on the research of this paper.