dc.contributor.author | Korhonen, Tuukka | |
dc.date.accessioned | 2024-08-01T08:48:29Z | |
dc.date.available | 2024-08-01T08:48:29Z | |
dc.date.created | 2023-04-27T09:41:02Z | |
dc.date.issued | 2023 | |
dc.identifier.issn | 0095-8956 | |
dc.identifier.uri | https://hdl.handle.net/11250/3144006 | |
dc.description.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(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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Grid induced minor theorem for graphs of small degree | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2023 The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 2 | |
dc.identifier.doi | 10.1016/j.jctb.2023.01.002 | |
dc.identifier.cristin | 2143721 | |
dc.source.journal | Journal of combinatorial theory. Series B (Print) | en_US |
dc.source.pagenumber | 206-214 | en_US |
dc.identifier.citation | Journal of combinatorial theory. Series B (Print). 2023, 160, 206-214. | en_US |
dc.source.volume | 160 | en_US |