Loading...
Please wait, while we are loading the content...
Similar Documents
A note on a problem of Erdos and Rothschild
| Content Provider | Semantic Scholar |
|---|---|
| Author | Potechin, Aaron |
| Copyright Year | 2014 |
| 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\H{o}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 \Omega\left(\min{\{\frac{n}{\sqrt{f(n)}}, \frac{n^2}{f(n)^2}\}}\right)$. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/1412.1838v1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
