Spanning trees in graphs without large bipartite holes

Abstract

We show that for any $\epsilon >0$ and $\Delta \in \mathbb{N}$, there exists $\alpha >0$ such that for sufficiently large $n$, every $n$-vertex graph $G$ satisfying that $\delta (G)\ge \epsilon n$ and $e(X,Y)>0$ for every pair of disjoint vertex sets $X,Y\subseteq V(G)$ of size $\alpha n$ contains all spanning trees with maximum degree at most $\Delta$. This strengthens a result of Böttcher et al.

17 pages, no figure