Maximum induced forests in graphs of bounded treewidth (Q396918): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 04:24, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum induced forests in graphs of bounded treewidth |
scientific article |
Statements
Maximum induced forests in graphs of bounded treewidth (English)
0 references
14 August 2014
0 references
Summary: Given a nonnegative integer \(d\) and a graph \(G\), let \(f_d(G)\) be the maximum order of an induced forest in \(G\) having maximum degree at most \(d\). We seek lower bounds for \(f_d(G)\) based on the order and treewidth of \(G\). We show that, for all \(k,d\geq 2\) and \(n\geq 1\), if \(G\) is a graph with order \(n\) and treewidth at most \(k\), then \(f_d(G)\geq\lceil{(2dn+2)/(kd+d+1)}\rceil\), unless \(G\in\{K_{1,1,3},K_{2,3}\}\) and \(k=d=2\). We give examples that show that this bound is tight to within 1. We conjecture a bound for \(d=1: f_1(G) \geq\lceil{2n/(k+2)}\rceil\), which would also be tight to within 1, and we prove it for \(k\leq 3\). For \(k\geq 4\) the conjecture remains open, and we prove a weaker bound: \(f_1(G)\geq (2n+2)/(2k+3)\). We also examine the cases \(d=0\) and \(k=0,1\). Lastly, we consider open problems relating to \(f_d\) for graphs on a given surface, rather than graphs of bounded treewidth.
0 references
treewidth
0 references
chordal graph
0 references
induced forest
0 references