Bollobás–Komlós conjecture on embedding bounded-bandwidth graphs

Let $H$ and $G$ be graphs with $|V(H)|=|V(G)|=n$, and write $\bw(H)$ for the band-width of $H$, $\chi(H)$ for its chromatic number, $\Delta(H)$ for its maximum degree, and $\delta(G)$ for the minimum degree of $G$. Bollobás–Komlós conjecture. For every $\gamma>0$ and positive integers $r$ and $\Delta$, there is a $\beta>0$ and an $n_0$ such that, whenever $n\ge n_0$, $\chi(H)\le r$, $\Delta(H)\le \Delta$, $\bw(H)<\beta n$, and $\delta(G)\ge (1-1/r+\gamma)n$, then $H$ is a subgraph of $G$. This conjecture proposes a minimum-degree condition guaranteeing the embedding of every bounded-degree, bounded-chromatic graph with sufficiently small band-width.