Induced minors and subpolynomial treewidth
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_ | 1866914409097461760 |
|---|---|
| author | Chudnovsky, Maria Codsi, Julien Fischer, David Lokshtanov, Daniel |
| author_facet | Chudnovsky, Maria Codsi, Julien Fischer, David Lokshtanov, Daniel |
| contents | Given a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-induced-minor-free if no induced minor of $G$ is isomorphic to a member of $\mathcal{H}$, We denote by $W_{t\times t}$ the $t$-by-$t$ hexagonal grid, and by $K_{t,t}$ the complete bipartite graph with both sides of the bipartition of size $t$. We show that the class of $\{K_{t,t},W_{t\times t}\}$-induced minor-free graphs with bounded clique number has subpolynomial treewidth. Specifically, we prove that for every integer $t$ there exist $ε\in (0,1]$ and $c \in \mathbb{N}$ such that every $n$-vertex $\{K_{t,t},W_{t\times t}\}$-induced minor-free graph with no clique of size $t$ has treewidth at most $2^{c\log^{1-ε}n}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18835 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Induced minors and subpolynomial treewidth Chudnovsky, Maria Codsi, Julien Fischer, David Lokshtanov, Daniel Combinatorics 05C75, 05C40, 05C85 Given a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-induced-minor-free if no induced minor of $G$ is isomorphic to a member of $\mathcal{H}$, We denote by $W_{t\times t}$ the $t$-by-$t$ hexagonal grid, and by $K_{t,t}$ the complete bipartite graph with both sides of the bipartition of size $t$. We show that the class of $\{K_{t,t},W_{t\times t}\}$-induced minor-free graphs with bounded clique number has subpolynomial treewidth. Specifically, we prove that for every integer $t$ there exist $ε\in (0,1]$ and $c \in \mathbb{N}$ such that every $n$-vertex $\{K_{t,t},W_{t\times t}\}$-induced minor-free graph with no clique of size $t$ has treewidth at most $2^{c\log^{1-ε}n}$. |
| title | Induced minors and subpolynomial treewidth |
| topic | Combinatorics 05C75, 05C40, 05C85 |
| url | https://arxiv.org/abs/2512.18835 |