Induced Subgraphs of Bounded Degree and Bounded Treewidth

Details Induced Subgraphs of Bounded Degree and Bounded Treewidth Induced Subgraphs of Bounded Degree and Bounded Treewidth

2005-05-19

arxiv.org/abs/math/0505415v1

Contributions to Discrete Mathematics, 1(1):88-105, 2006.

Mathematics

Combinatorics

A short version of this paper will appear in the proceedings of WG 2005 (Lecture Notes in Computer Science, Springer)

Scientific paper

We prove that for all $0\leq t\leq k$ and $d\geq 2k$, every graph $G$ with treewidth at most $k$ has a `large' induced subgraph $H$, where $H$ has treewidth at most $t$ and every vertex in $H$ has degree at most $d$ in $G$. The order of $H$ depends on $t$, $k$, $d$, and the order of $G$. With $t=k$, we obtain large sets of bounded degree vertices. With $t=0$, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of $H$ are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size $k$ has a maximum independent set in which every vertex has degree at most $2k$.

Affiliated with

Also associated with

No associations

Rating

Induced Subgraphs of Bounded Degree and Bounded Treewidth 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 Induced Subgraphs of Bounded Degree and Bounded Treewidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Induced Subgraphs of Bounded Degree and Bounded Treewidth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-582072