Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917728473841664 |
|---|---|
| author | Bonnet, Édouard Hodor, Jędrzej Korhonen, Tuukka Masařík, Tomáš |
| author_facet | Bonnet, Édouard Hodor, Jędrzej Korhonen, Tuukka Masařík, Tomáš |
| contents | A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ after vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor and $K_{t,t}$ as a subgraph has treewidth at most $Δ(G)^{f(k,t)}$ where $Δ(G)$ denotes the maximum degree of $G$. Without requiring the absence of a $K_{t,t}$ subgraph, Korhonen [JCTB '23] has shown the upper bound of $k^{O(1)} 2^{Δ(G)^5}$ whose dependence in $Δ(G)$ is exponential. Our result partially answers a question of Chudnovsky [Dagstuhl seminar '23] asking whether the treewidth of graphs with $Δ(G)=O(\log{|V(G)|})$ excluding both a $k$-vertex planar graph as an induced minor and the biclique $K_{t,t}$ as a subgraph is in $O_{k,t}(\log |V(G)|)$. We confirm that the treewidth is in this case polylogarithmic in $|V(G)|$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07962 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor Bonnet, Édouard Hodor, Jędrzej Korhonen, Tuukka Masařík, Tomáš Combinatorics Discrete Mathematics Data Structures and Algorithms 05C83 G.2.2 A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ after vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor and $K_{t,t}$ as a subgraph has treewidth at most $Δ(G)^{f(k,t)}$ where $Δ(G)$ denotes the maximum degree of $G$. Without requiring the absence of a $K_{t,t}$ subgraph, Korhonen [JCTB '23] has shown the upper bound of $k^{O(1)} 2^{Δ(G)^5}$ whose dependence in $Δ(G)$ is exponential. Our result partially answers a question of Chudnovsky [Dagstuhl seminar '23] asking whether the treewidth of graphs with $Δ(G)=O(\log{|V(G)|})$ excluding both a $k$-vertex planar graph as an induced minor and the biclique $K_{t,t}$ as a subgraph is in $O_{k,t}(\log |V(G)|)$. We confirm that the treewidth is in this case polylogarithmic in $|V(G)|$. |
| title | Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C83 G.2.2 |
| url | https://arxiv.org/abs/2312.07962 |