Illingworth, Freddie;
(2021)
Graphs with no induced K2,t.
Electronic Journal of Combinatorics
, 28
(1)
, Article P1.19. 10.37236/9223.
Preview |
Text
induced_K2t_EJC.pdf - Published Version Download (288kB) | Preview |
Abstract
CConsider a graph G on n vertices with α α n 2 edges which does not contain an induced K2,t (t > 2). How large must α be to ensure that G contains, say, a large clique or some fixed subgraph H? We give results for two regimes: for α bounded away from zero and for α = o(1). Our results for α = o(1) are strongly related to the Induced Tur´an numbers which were recently introduced by Loh, Tait, Timmons and Zhou. For α 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).
| Type: | Article |
|---|---|
| Title: | Graphs with no induced K2,t |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.37236/9223 |
| Publisher version: | http://dx.doi.org/10.37236/9223 |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Science & Technology, Physical Sciences, Mathematics, Applied, Mathematics, NUMBER |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10189640 |
Archive Staff Only
 |
View Item |
