A note on a problem of Erdos and Rothschild

Abstract

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)\ge \Omega \left(\min \{\frac{n}{\sqrt{f(n)}},\frac{n^2}{f(n{)}^2}\}\right)$.

7 pages, 0 figures

References in corpus (1)

• A note on Ramsey Numbers for Books