Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912570169884672 |
|---|---|
| author | Choi, Mujin Wiederrecht, Sebastian |
| author_facet | Choi, Mujin Wiederrecht, Sebastian |
| contents | A $k$-ladder is the graph obtained from two disjoint paths, each with $k$ vertices, by joining the $i$th vertices of both paths with an edge for each $i\in\{ 1,\ldots,k\}$. In this paper, we show that for all positive integers $k$ and $d$, the class of all $K_{1,d}$-free graphs excluding the $k$-ladder as an induced minor has a bounded tree-independence number.
We further show that our method implies a number of known results: We improve the bound on the tree-independence number for the class of $K_{1,d}$-free graphs not containing a wheel as an induced minor given by Choi, Hilaire, Milanič, and Wiederrecht. Furthermore, we show that the class of $K_{1,d}$-free graphs not containing a theta or a prism, whose paths have length at least $k$, as an induced subgraph has bounded tree-independence number. This improves a result by Chudnovsky, Hajebi, and Trotignon. Finally, we extend the induced Erdős-Pósa result of Ahn, Gollin, Huynh, and Kwon in $K_{1,d}$-free graphs from long induced cycles to any graph that is an induced minor of the $k$-ladder where every edge is subdivided exactly once. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04026 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars Choi, Mujin Wiederrecht, Sebastian Combinatorics Discrete Mathematics 05C75 05C83 05C85 68R10 G.2.2; F.2.2; G.2.1 A $k$-ladder is the graph obtained from two disjoint paths, each with $k$ vertices, by joining the $i$th vertices of both paths with an edge for each $i\in\{ 1,\ldots,k\}$. In this paper, we show that for all positive integers $k$ and $d$, the class of all $K_{1,d}$-free graphs excluding the $k$-ladder as an induced minor has a bounded tree-independence number. We further show that our method implies a number of known results: We improve the bound on the tree-independence number for the class of $K_{1,d}$-free graphs not containing a wheel as an induced minor given by Choi, Hilaire, Milanič, and Wiederrecht. Furthermore, we show that the class of $K_{1,d}$-free graphs not containing a theta or a prism, whose paths have length at least $k$, as an induced subgraph has bounded tree-independence number. This improves a result by Chudnovsky, Hajebi, and Trotignon. Finally, we extend the induced Erdős-Pósa result of Ahn, Gollin, Huynh, and Kwon in $K_{1,d}$-free graphs from long induced cycles to any graph that is an induced minor of the $k$-ladder where every edge is subdivided exactly once. |
| title | Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars |
| topic | Combinatorics Discrete Mathematics 05C75 05C83 05C85 68R10 G.2.2; F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2509.04026 |