Maximum induced forests in graphs of bounded treewidth (Q396918): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
Added link to MaRDI item.
links / mardi / namelinks / 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
    0 references
    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

    Identifiers