2023/10/27 by António Girão, Zach Hunter, Girão, António +1 · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.18452
openalex publication_date 2023/10/27 · openalex created_date 2023/11/01 · openalex updated_date 2026/07/28
In this paper we prove that for every s≥ 2 and every graph H the following holds. Let G be a graph with average degree ΩH(sC|H|2), for some absolute constant C>0, then G either contains a Ks,s or an induced subdivision of H. This is essentially tight and confirms a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak. A slightly weaker form of this has been independently proved by Bourneuf, Bucić, Cook, and Davies. We actually prove a much more general result which implies the above (with worse dependence on |H|). We show that for every k≥ 2 there is Ck>0 such that any graph G with average degree sCk either contains a Ks,s or an induced subgraph G'⊆ G without C4's and with average degree at least k. Finally, using similar methods we can prove the following. For every k,t≥ 2 every graph G with average degree at least CtkΩ(t) must contain either a Kk, an induced Kt,t or an induced subdivision of Kk. This is again essentially tight up to the implied constants and answers in a strong form a question of Davies.