pith. sign in

arxiv: 0707.2522 · v1 · submitted 2007-07-17 · 🧮 math.CO

On embedding well-separable graphs

classification 🧮 math.CO
keywords deltawell-separablegraphordergammagraphssimplesize
0
0 comments X
read the original 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-{1 \over 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.