Grid Induced Minor Theorem for Graphs of Small Degree
share
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 × 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.
READ FULL TEXT