On embedding well-separable graphs

Details On embedding well-separable graphs On embedding well-separable graphs

2007-07-17

arxiv.org/abs/0707.2522v1

Mathematics

Combinatorics

11 pages, submitted for publication

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On embedding well-separable graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On embedding well-separable graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On embedding well-separable graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-562959