Maximum induced forests in graphs of bounded treewidth

MaRDI QIDQ396918zbMATH OpenFDO

Authors Glenn G. Chappell, Michael J. Pelsmajer

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p8

zbMATH Keywords

treewidthchordal graphinduced forest

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Recommendations

• On maximum induced forests in graphs
• Maximum induced forests of planar graphs
• Maximum induced trees in graphs
• Maximum induced forests in random graphs
• A better bound on the largest induced forests in triangle-free planar graph
• Maximum induced linear forests in outerplanar graphs
• An improved bound on the largest induced forests for triangle-free planar graphs
• Induced Forests in Regular Graphs with Large Girth
• scientific article; zbMATH DE number 9665
• A lower bound on the order of the largest induced forest in planar graphs with high girth

Cites work

• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 9665 (Why is no real title available?)
• scientific article; zbMATH DE number 3536160 (Why is no real title available?)
• scientific article; zbMATH DE number 3565019 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 1744105 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Acyclic colorings of planar graphs
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Independent sets in triangle-free cubic planar graphs
• Induced subgraphs of bounded degree and bounded treewidth
• Large induced forests in sparse graphs
• Large induced forests in triangle-free planar graphs
• Maximum induced forests of planar graphs
• Maximum induced linear forests in outerplanar graphs
• Minimum feedback vertex set and acyclic coloring.
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• On acyclic colorings of planar graphs
• On the linear vertex-arboricity of a planar graph
• Size and independence in triangle‐free graphs with maximum degree three
• Some Ramsey-Type Numbers and the Independence Ratio
• Threshold for path colorings of planar graphs

Cited in

(12)

• Product dimension of forests and bounded treewidth graphs
• scientific article; zbMATH DE number 1375581 (Why is no real title available?)
• Induced subgraphs of bounded degree and bounded treewidth
• On maximum induced forests in graphs
• On the maximum induced forests of a connected cubic graph without triangles
• The \(k\)-strong induced arboricity of a graph
• Maximum induced forests of planar graphs
• On the maximum orders of an induced forest, an induced tree, and a stable set
• Graph-Theoretic Concepts in Computer Science
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• Well-indumatched Trees and Graphs of Bounded Girth
• Maximal trees with bounded maximum degree in a graph

This page was built for publication: Maximum induced forests in graphs of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396918)