Grid induced minor theorem for graphs of small degree
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/3144006/1-s2.0-S0095895623000047-main.pdf.jpg?sequence=6&isAllowed=y)
View/ Open
Date
2023Metadata
Show full item recordCollections
- Department of Informatics [979]
- Registrations from Cristin [10327]
Original version
Journal of combinatorial theory. Series B (Print). 2023, 160, 206-214. 10.1016/j.jctb.2023.01.002Abstract
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(k10 +2d5 ) 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 (2021) [1] 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.