图的平面Turán数和平面anti-Ramsey数

在所有顶点数为n且不包含图G作为子图的平面图中,具有最多边数的图的边数称为图G的平面Turán数,记为exP(n,G)。给定正整数n以及平面图H,用Tn(H)来表示所有顶点数为n且不包含H作为子图的平面三角剖分图所组成的图集合。设图集合Tn(H)中的任意平面三角剖分图的任意k边染色都不包含彩虹子图H,则称满足上述条件的k的最大值为图H的平面anti-Ramsey数,记作arP(n,H)。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。

Turán number of Berge linear forests in uniform hypergraphs

t Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edges in an r-uniform hypergraph of order n that is Berge-F-free,denoted by ex,(n,Berge-F).A linear forest is a graph whose connected components are all paths or isolated vertices.Let Ln,k be the family of all linear forests of n vertices with k edges.In this paper,Turan number of Berge-Ln,in an r-uniform hypergraph is studied.When r≥k+1 and 3≤r≤l[]=1,we determine 2 the exact value of ex,(n,Berge-Ln,)respectively.When K-1≤r≤k,we 2 determine the upper bound of ex,(n,Berge-Ln,).

The <i>H</i>-Decomposition Problem for Graphs

The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.

Extremal P_(8)-Free/P_(9)-Free Planar Graphs

An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.

Turán Problems for Berge-(k,p)-Fan Hypergraph

Let F be a graph.A hypergraph H is Berge-F if there is a bijection f:E(F)→E(H)such that e■f(e)for every e∈E(F).A hypergraph is Berge-F-free if it does not contain a subhypergraph isomorphic to a Berge-F hypergraph.The authors denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by ex_(r)(n,Berge-F).A(k,p)-fan,denoted by F_(k,p),is a graph on k(p-1)+1 vertices consisting of k cliques with p vertices that intersect in exactly one common vertex.In this paper they determine the bounds of ex_(r)(n,Berge-F)when F is a(k,p)-fan for k≥2,p≥3 and r≥3.

The Maximum Lagrangian of 5-uniform Hypergraphs without Containing Two Edges Intersecting at a Vertex

Obtaining Turán densities of hypergraph through determining Lagrangian densities have been studied actively.Sidorenko showed that the Lagrangian density of an r-uniform hypergraph equals the Turán density of the extension of this hypergraph.Indeed,Lagrangian density and Turán density are the same for a large class of hypergraphs such as hypergraphs covering pairs.Let Pr,sbe the r-uniform hypergraph with two edges intersecting at s vertices.Sidorenko determined the Lagrangian densities of Pr,sfor r=3 and s=1 or 2,or r=4 and s=2 or 3.Hefetz and Keevash determined for r=3 and s=0,and Bene Watts,Norin and Yepremyan determined for r≥4 and s=0.The cases r=5 and s=4 or r=6 and s=5 were determined by Norin and Yepremyan.Jenssen showed for r=5,6 or 7,and s=3,4 or 5 respectively.The cases r=4 and s=1 or r=5 and s=2 were determined by Jiang,Peng and Wu,and Hu,Peng and Wu respectively.For r=5,the only remaining case is s=1.In this paper,we determine for this case.