Excluding a Forest Induced Minor
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911296480346112 |
|---|---|
| author | Bonnet, Édouard Duhamel, Benjamin Hickingbotham, Robert |
| author_facet | Bonnet, Édouard Duhamel, Benjamin Hickingbotham, Robert |
| contents | In the first paper of the Graph Minors series [JCTB '83], Robertson and Seymour proved the Forest Minor theorem: the $H$-minor-free graphs have bounded pathwidth if and only if $H$ is a forest. In recent years, considerable effort has been devoted to understanding the unavoidable induced substructures of graphs with large pathwidth or large treewidth. In this paper, we give an induced counterpart of the Forest Minor theorem: for any $t \geqslant 2$, the $K_{t,t}$-subgraph-free $H$-induced-minor-free graphs have bounded pathwidth if and only if $H$ belongs to a class $\mathcal F$ of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs $H$ for which every weakly sparse $H$-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01857 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Excluding a Forest Induced Minor Bonnet, Édouard Duhamel, Benjamin Hickingbotham, Robert Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75, 05C83, 05C85 G.2.2 In the first paper of the Graph Minors series [JCTB '83], Robertson and Seymour proved the Forest Minor theorem: the $H$-minor-free graphs have bounded pathwidth if and only if $H$ is a forest. In recent years, considerable effort has been devoted to understanding the unavoidable induced substructures of graphs with large pathwidth or large treewidth. In this paper, we give an induced counterpart of the Forest Minor theorem: for any $t \geqslant 2$, the $K_{t,t}$-subgraph-free $H$-induced-minor-free graphs have bounded pathwidth if and only if $H$ belongs to a class $\mathcal F$ of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs $H$ for which every weakly sparse $H$-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series. |
| title | Excluding a Forest Induced Minor |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75, 05C83, 05C85 G.2.2 |
| url | https://arxiv.org/abs/2512.01857 |