On embedding well-separable graphs

Abstract

Call a simple graph $H$ of order $n$ well-separable, if by deleting a separator set of size $o(n)$ the leftover will have components of size at most $o(n)$. We prove, that bounded degree well-separable spanning subgraphs are easy to embed: for every $\gamma >0$ and positive integer $\Delta$ there exists an $n_0$ such that if $n>n_0$, $\Delta (H)\le \Delta$ for a well-separable graph $H$ of order $n$ and $\delta (G)\ge (1-\frac{1}{2(\chi (H)-1)}+\gamma )n$ for a simple graph $G$ of order $n$, then $H\subset G$. We extend our result to graphs with small band-width, too.

11 pages, submitted for publication