Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.17232 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915685980962816 |
|---|---|
| author | Hickingbotham, Robert Joret, Gwenaël |
| author_facet | Hickingbotham, Robert Joret, Gwenaël |
| contents | Given a graph $G$ and $\mathcal{A}\subseteq V(G)$, a classical theorem of Gallai (1964) states that for every positive integer $k$, the graph $G$ contains $k$ pairwise vertex-disjoint $\mathcal{A}$-paths, or a set $Z\subseteq V(G)$ of size at most $2(k-1)$ such that $G-Z$ contains no $\mathcal{A}$-paths. We generalise Gallai's theorem to the induced setting: We prove that $G$ contains $k$ pairwise anti-complete $\mathcal{A}$-paths, or a set $Z$ of size at most $78(k-1)$ such that, after removing the closed neighbourhood of $Z$, the resulting graph has no $\mathcal{A}$-path. Here, two paths are anti-complete if they are vertex disjoint and there is no edge in $G$ having one endpoint in each of them.
We further show that the bound $78(k-1)$ on the size of $Z$ can be reduced to $4(k-1)$ if one removes the balls of radius $4$ around the vertices of $Z$ (instead of radius $1$), which is within a factor $2$ of optimal. We also establish analogous results for long induced $\mathcal{A}$-paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17232 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Induced $A$-Path Theorem Hickingbotham, Robert Joret, Gwenaël Combinatorics Given a graph $G$ and $\mathcal{A}\subseteq V(G)$, a classical theorem of Gallai (1964) states that for every positive integer $k$, the graph $G$ contains $k$ pairwise vertex-disjoint $\mathcal{A}$-paths, or a set $Z\subseteq V(G)$ of size at most $2(k-1)$ such that $G-Z$ contains no $\mathcal{A}$-paths. We generalise Gallai's theorem to the induced setting: We prove that $G$ contains $k$ pairwise anti-complete $\mathcal{A}$-paths, or a set $Z$ of size at most $78(k-1)$ such that, after removing the closed neighbourhood of $Z$, the resulting graph has no $\mathcal{A}$-path. Here, two paths are anti-complete if they are vertex disjoint and there is no edge in $G$ having one endpoint in each of them. We further show that the bound $78(k-1)$ on the size of $Z$ can be reduced to $4(k-1)$ if one removes the balls of radius $4$ around the vertices of $Z$ (instead of radius $1$), which is within a factor $2$ of optimal. We also establish analogous results for long induced $\mathcal{A}$-paths. |
| title | An Induced $A$-Path Theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.17232 |