The study of sufficient degree conditions, on a given graph G, which imply that G contains a particular spanning subgraph H is one of the central areas in graph theory. A well known example of such a result is Dirac’s theorem. It asserts that any graph G on n vertices with minimum degree at least n/2 contains a spanning, so called Hamiltonian, cycle.

In my talk we discuss related results for graphs H of bounded maximum degree and small bandwidth. In particular we show that: For all integers k and Δ and γ > 0 there exist a constant β > 0 such that for sufficiently large n the following holds. If G is an n-vertex graph with minimum degree δ(G) ≥ ((k −1)/k +γ)n, then it contains a spanning copy of every k-chromatic n-vertex graph H with maximum degree Δ(H) ≤ Δ and bandwidth bw(H) at most βn, where bw(H) = min_{σ} max_{uv∈E(H)} |σ(u) − σ(v)| with the minimum ranging over all bijections from V (H) to [n]. This settles a conjecture of Bollobás and Komlós. It is known that the minimum degree condition on G is asymptotically best possible.

The proof is based on Szemerédi’s regularity lemma and the so called Blowup lemma. This is joint work with Julia Böttcher and Anusch Taraz from TU-München.