Author/Authors :
Bollobلs، نويسنده , , Béla and Nikiforov، نويسنده , , Vladimir، نويسنده ,
Abstract :
A set of q triangles sharing a common edge is called a book of size q. We write β(n,m) for the maximal q such that every graph G(n,m) contains a book of size q. In this note
compute β(n,cn2) for infinitely many values of c with 1/4<c<1/3,
show that if m≥(1/4−α)n2 with 0<α<17−3, and G has no book of size at least (1/6−2α1/3)n then G contains an induced bipartite graph G1 of order at least (1−α1/3)n and minimal degreeδ(G1)≥12−4α1/3n,
apply the latter result to answer two questions of Erdős concerning the booksize of graphs G(n,n2/4−f(n)n) every edge of which is contained in a triangle, and 0<f(n)<n2/5−ε.