On embedding well-separable graphs
| dc.creator | Csaba, Béla | |
| dc.date | 2007-07-17 | |
| dc.date.accessioned | 2026-07-07T08:18:46Z | |
| dc.date.available | 2026-07-07T08:18:46Z | |
| dc.description | 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 $γ>0$ and positive integer $Δ$ there exists an $n_0$ such that if $n>n_0$, $Δ(H) \le Δ$ for a well-separable graph $H$ of order $n$ and $δ(G) \ge (1-{1 \over 2(χ(H)-1)} + γ)n$ for a simple graph $G$ of order $n$, then $H \subset G$. We extend our result to graphs with small band-width, too. | |
| dc.description | 11 pages, submitted for publication | |
| dc.identifier | https://arxiv.org/abs/0707.2522 | |
| dc.identifier | http://arxiv.org/abs/0707.2522 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134548 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35 | |
| dc.title | On embedding well-separable graphs | |
| dc.type | text |