2014/12/04 by Aaron Potechin, Potechin, Aaron
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1412.1838
7 pages, 0 figures
arxiv created 2014/12/04 · arxiv updated 2014/12/08
A set of q triangles sharing a common edge is a called a book of size q. Letting bk(G) denote the size of the largest book in a graph G, Erdős and Rothschild \citeerdostwo asked what the minimal value of bk(G) is for graphs G with n vertices and a set number of edges where every edge is contained in at least one triangle. In this paper, we show that for any graph G with n vertices and (n2)/(4) - nf(n) edges where every edge is contained in at least one triangle, bk(G) ≥ Ω(min\(n)/(√(f(n))), (n2)/(f(n)2)\).