A note on a problem of Erdos and Rothschild

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 \cite{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 $\frac{n^2}{4} - nf(n)$ edges where every edge is contained in at least one triangle, $bk(G) \geq Ω\left(\min{\{\frac{n}{\sqrt{f(n)}}, \frac{n^2}{f(n)^2}\}}\right)$.

No reviews yet.

No comments yet.