On embedding well-separable graphs Original Research Article

Call a simple graph image of order image well-separable, if by deleting a separator set of size image the leftover will have components of size at most image. We prove, that bounded degree well-separable spanning subgraphs are easy to embed: for every image and positive integer image there exists an image such that if image, image for a well-separable graph image of order image and image for a simple graph image of order image, then image. We extend our result to graphs with small band-width, too.