Sparse induced subgraphs of large treewidth

DOI10.1016/J.JCTB.2025.03.002MaRDI QIDQ6987041zbMATH OpenFDO

Authors Édouard Bonnet

Publication date 7 May 2025

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTB.2025.03.002

zbMATH Keywords

induced subgraphssparsitytreewidth

Mathematics Subject Classification ID

Trees (05C05) Density (toughness, etc.) (05C42) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites work

• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• A single-exponential time 2-approximation algorithm for treewidth
• Contraction obstructions for treewidth
• Degree-3 treewidth sparsifiers
• Graph minors. V. Excluding a planar graph
• Graph searching and a min-max theorem for tree-width
• Grid induced minor theorem for graphs of small degree
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Induced subdivisions and bounded expansion
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
• Induced-minor-free graphs: separator theorem, subexponential algorithms, and improved hardness of recognition
• On a problem of formal logic.
• On the tree-width of even-hole-free graphs
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Sparsity. Graphs, structures, and algorithms
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

This page was built for publication: Sparse induced subgraphs of large treewidth

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