Grid Induced Minor Theorem for Graphs of Small Degree

Abstract

A graph $H$ is an induced minor of a graph $G$ if $H$ can be obtained from $G$ by vertex deletions and edge contractions. We show that there is a function $f(k,d)=O(k^{10}+2^{d^5})$ so that if a graph has treewidth at least $f(k,d)$ and maximum degree at most $d$, then it contains a $k\times k$-grid as an induced minor. This proves the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon [Eur. J. Comb., 98, 2021] that any graph with large treewidth and bounded maximum degree contains a large wall or the line graph of a large wall as an induced subgraph. It also implies that for any fixed planar graph $H$, there is a subexponential time algorithm for maximum weight independent set on $H$-induced-minor-free graphs.

7 pages. To appear in JCTB

Cited by in corpus (10)

• Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs
• Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Induced subgraphs and tree decompositions V. One neighbor in a hole
• Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs
• Twin-width of subdivisions of multigraphs
• Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
• Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
• Maximum Independent Set when excluding an induced minor: $K_1+t{K}_2$ and $t{C}_3\uplus C_4$
• $t$-sails and sparse hereditary classes of unbounded tree-width