Grid induced minor theorem for graphs of small degree
From MaRDI portal
Publication:2692786
DOI10.1016/j.jctb.2023.01.002OpenAlexW4317938275MaRDI QIDQ2692786
Publication date: 23 March 2023
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2203.13233
Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree ⋮ Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs ⋮ Induced subgraphs and path decompositions ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole
Cites Work
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Face covers and the genus problem for apex graphs
- On the tree-width of even-hole-free graphs
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- Towards tight(er) bounds for the excluded grid theorem
- Contraction obstructions for treewidth
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Polynomial Bounds for the Grid-Minor Theorem
- Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
- Degree-3 Treewidth Sparsifiers
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time
This page was built for publication: Grid induced minor theorem for graphs of small degree
