Grid induced minor theorem for graphs of small degree

DOI10.1016/j.jctb.2023.01.002OpenAlexW4317938275MaRDI QIDQ2692786

Tuukka Korhonen

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

zbMATH Keywords

treewidthgridinduced minor

Mathematics Subject Classification ID

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