Erdős-Pósa property of tripods in directed graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914928973053952 |
|---|---|
| author | Briański, Marcin Hatzel, Meike Okrasa, Karolina Pilipczuk, Michał |
| author_facet | Briański, Marcin Hatzel, Meike Okrasa, Karolina Pilipczuk, Michał |
| contents | Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$. A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix.
We prove that tripods in directed graphs exhibit the Erdős-Pósa property. More precisely, there is a function $f\colon \mathbb{N}\to \mathbb{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16733 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Erdős-Pósa property of tripods in directed graphs Briański, Marcin Hatzel, Meike Okrasa, Karolina Pilipczuk, Michał Combinatorics Discrete Mathematics Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$. A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix. We prove that tripods in directed graphs exhibit the Erdős-Pósa property. More precisely, there is a function $f\colon \mathbb{N}\to \mathbb{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$. |
| title | Erdős-Pósa property of tripods in directed graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2408.16733 |