Author
Illingworth, F
Journal title
The Electronic Journal of Combinatorics
DOI
10.37236/9223
Issue
1
Volume
28
Last updated
2023-10-28T03:32:48.04+01:00
Abstract
<jats:p>Consider a graph $G$ on $n$ vertices with $\alpha \binom{n}{2}$ edges which does not contain an induced $K_{2, t}$ ($t \geqslant 2$). How large must $\alpha$ be to ensure that $G$ contains, say, a large clique or some fixed subgraph $H$? We give results for two regimes: for $\alpha$ bounded away from zero and for $\alpha = o(1)$.&#x0D;
Our results for $\alpha = o(1)$ are strongly related to the Induced Turán numbers which were recently introduced by Loh, Tait, Timmons and Zhou. For $\alpha$ bounded away from zero, our results can be seen as a generalisation of a result of Gyárfás, Hubenko and Solymosi and more recently Holmsen (whose argument inspired ours).</jats:p>
Symplectic ID
1198573
Favourite
Off
Publication type
Journal Article
Publication date
29 Jan 2021
Please contact us with feedback and comments about this page. Created on 04 Oct 2021 - 18:46.