Maximum induced forests in graphs of bounded treewidth (Q396918): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6330339 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
treewidth | |||
Property / zbMATH Keywords: treewidth / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
chordal graph | |||
Property / zbMATH Keywords: chordal graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
induced forest | |||
Property / zbMATH Keywords: induced forest / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4111622 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Large induced forests in sparse graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximum induced forests of planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529530 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A partial k-arboretum of graphs with bounded treewidth / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4137202 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On acyclic colorings of planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5480768 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New bounds on the size of the minimum feedback vertex set in meshes and butterflies. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3424891 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4947393 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3872499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimum feedback vertex set and acyclic coloring. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Acyclic colorings of planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Independent sets in triangle-free cubic planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3971782 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Size and independence in triangle‐free graphs with maximum degree three / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding independent sets in \(K_4\)-free 4-regular connected graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximum induced linear forests in outerplanar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the linear vertex-arboricity of a planar graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4352948 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Large induced forests in triangle-free planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Ramsey-Type Numbers and the Independence Ratio / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 22:17, 8 July 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