• Title of article

    Books in graphs

  • Author/Authors

    Bollobلs، نويسنده , , Béla and Nikiforov، نويسنده , , Vladimir، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2005
  • Pages
    12
  • From page
    259
  • To page
    270
  • 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−ε.
  • Journal title
    European Journal of Combinatorics
  • Serial Year
    2005
  • Journal title
    European Journal of Combinatorics
  • Record number

    1546991