A note on a problem of Erdos and Rothschild

Original · EN

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 erdostwo 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 n²/4 - nf(n) edges where every edge is contained in at least one triangle, bk(G) ≥ Ω({n√f(n), n²/f(n)²}).