The bandwidth theorem for locally dense graphs
2020; Cambridge University Press; Volume: 8; Linguagem: Inglês
10.1017/fms.2020.39
ISSN2050-5094
AutoresKatherine Staden, Andrew Treglown,
Tópico(s)Advanced Topology and Set Theory
ResumoThe Bandwidth theorem of B\"ottcher, Schacht and Taraz gives a condition on the minimum degree of an $n$-vertex graph $G$ that ensures $G$ contains every $r$-chromatic graph $H$ on $n$ vertices of bounded degree and of bandwidth $o(n)$, thereby proving a conjecture of Bollob\'as and Koml\'os. In this paper we prove a version of the Bandwidth theorem for locally dense graphs. Indeed, we prove that every locally dense $n$-vertex graph $G$ with $\delta (G) > (1/2+o(1))n$ contains as a subgraph any given (spanning) $H$ with bounded maximum degree and sublinear bandwidth.
Referência(s)