Excluding an induced wheel minor in graphs without large induced stars
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_ | 1866915335407403008 |
|---|---|
| author | Choi, Mujin Hilaire, Claire Milanič, Martin Wiederrecht, Sebastian |
| author_facet | Choi, Mujin Hilaire, Claire Milanič, Martin Wiederrecht, Sebastian |
| contents | We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer $d$ and any planar graph $H$, the class of all $K_{1,d}$-free graphs without $H$ as an induced minor has bounded tree-independence number. A $k$-wheel is the graph obtained from a cycle of length $k$ by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when $H$ is a $k$-wheel for any $k\geq 3$. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important $\mathsf{NP}$-hard problems such as Maximum Independent Set are tractable on $K_{1,d}$-free graphs without large induced wheel minors. Moreover, for fixed $d$ and $k$, we provide a polynomial-time algorithm that, given a $K_{1,d}$-free graph $G$ as input, finds an induced minor model of a $k$-wheel in $G$ if one exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08829 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Excluding an induced wheel minor in graphs without large induced stars Choi, Mujin Hilaire, Claire Milanič, Martin Wiederrecht, Sebastian Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75 (Primary), 05C83, 05C69, 05C05, 05C85 (Secondary) We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer $d$ and any planar graph $H$, the class of all $K_{1,d}$-free graphs without $H$ as an induced minor has bounded tree-independence number. A $k$-wheel is the graph obtained from a cycle of length $k$ by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when $H$ is a $k$-wheel for any $k\geq 3$. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important $\mathsf{NP}$-hard problems such as Maximum Independent Set are tractable on $K_{1,d}$-free graphs without large induced wheel minors. Moreover, for fixed $d$ and $k$, we provide a polynomial-time algorithm that, given a $K_{1,d}$-free graph $G$ as input, finds an induced minor model of a $k$-wheel in $G$ if one exists. |
| title | Excluding an induced wheel minor in graphs without large induced stars |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75 (Primary), 05C83, 05C69, 05C05, 05C85 (Secondary) |
| url | https://arxiv.org/abs/2506.08829 |