Grid Induced Minor Theorem for Graphs of Small Degree

DOI10.1016/J.JCTB.2023.01.002arXiv2203.13233MaRDI QIDQ6394641

Tuukka Korhonen

Publication date: 24 March 2022

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 $kimesk$-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.

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)

This page was built for publication: Grid Induced Minor Theorem for Graphs of Small Degree

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