Turán Type Extremal Graph Problems

Extremal graph theory is a branch of the discrete mathematical field of graph theory.Extremal graph theory studies extremal(maximal or minimal)graphs which satisfy a certain property.Extremality can be taken with respect to different graph invariants,such as order,size or girth.More abstractly,it studies how global properties of a graph influence local substructures of the graph.In this dissertation we will focus on the Turan-type extremal graph problems and the anti-Ramsey problems.· The Turan number of a graph H,ex(n,H),is the maximum number of edges in any graph of order n which does not contain H as a subgraph.Turan theorem is a cornerstone of the extremal graph theory.It asserts that the extremal graph without containing Kp+1 as a subgraph is the complete p-partite graph on n vertices which is balanced,in that the part sizes are as equal as possible(any two sizes differ by at most 1).In chapter 2 of this paper,we give some proofs of the Turan theorem and we also give a new proof of Turan theorem.· In chapter 3 of this paper,we will consider the Turan number of a graph H when x(H)≥3.A classical theorem of Erdos,Stone and Simonovits shows that if L is a set of graphs with min{x(L):L GL}-1 =p,then ex(n,L)=e(Tp(n))+o(n2).The decomposition family of L,M(L),is the family of minimal graphs M that satisfy the following:there exist an L∈ L and a large t = t(L)such that L C M+Tp-1(pt-t).Base on Simonovits’ progressive induction method,we determined the Turan number of C when ex(n,M(L))is independent of n or L = {Sk+1}.Bases on those results,we give a new proof of the Turan number of the intersecting cliques and the determination of the extremal graphs is also new.In second part of chapter 3 in this paper,we determine the Turan number of k-flower(a graph consisting of k cycles which intersect in exactly one common vertex is called a k-flower.)containing at least one odd cycle and characterize all extremal graphs for n sufficiently large.Given a graph H and an integer p,the edge blow-up of H,denoted as Hp+1,is the graph obtained from replacing each edge in H by a clique of size p+ 1 where the new vertices of the cliques are all different.In the third part of chapter 3,we determined Turan number of the edge blow-up of any graph.· The Erdos-Sos Conjecture states that if G is a simple graph of order n with average degree more than k-2,then G contains every tree of order k.In first part of chapter 4 in this paper,we prove that Erdos-Sos Conjecture is true for n = k+4.In second part of chapter 4 in this paper,we consider a variation of the above conjecture:studying the maximum size of an(n,m)-bipartite graph which does not contain all(k,l)-bipartite trees for given integers n≥m and k≥1.In particular,we determine that the maximum size of an(n,m)-bipartite graph which does not contain all(n,m)-bipartite trees as subgraphs(all(k,2)-bipartite trees as subgraphs or all(3,3)-bipartite trees as subgraphs,respectively).Furthermore,all these extremal graphs are characterized.· In chapter 5,we determine the Turan number of some linear forests.Let k·P3 denote k disjoint copies of a path on three vertices.In the first part of this chapter7,we determine the value ex(n,k ·P3)and characterize all extremal graphs for all k and n which confirms the conjecture proposed by Gorgol.Let Fm be disjoint paths of Pk1,...,Pkm.In second part of chapter 5 in this paper,we determine ex(n,F.)for all integers n with minor conditions.· The anti-Ramsey number of a graph H,AR(n,H),is the maximum number of colors in an edge-coloring of K,which does not contain a polychromatic copy of H.In chapter 6 of this paper,we determine anti-Ramsey numbers for new families of graph,and characterize the extremal colorings which extends the results of Jiang and Pikhurko.