A star-comb lemma for infinite digraphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913891209969664 |
|---|---|
| author | Reich, Florian |
| author_facet | Reich, Florian |
| contents | The star-comb lemma is a standard tool in infinite graph theory, which states that for every infinite set $U$ of vertices in a connected graph $G$ there exists either a subdivided infinite star in $G$ with all leaves in $U$, or an infinite comb in $G$ with all teeth in $U$.
In this paper, we elaborate a counterpart of the star-comb lemma for directed graphs. More precisely, we prove that for every infinite set $U$ of vertices in a strongly connected directed graph $D$, there exists a strongly connected butterfly minor of $D$ with infinitely many teeth in $U$ that is either shaped by a star or shaped by a comb, or is a chain of triangles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04877 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A star-comb lemma for infinite digraphs Reich, Florian Combinatorics 05C20, 05C40, 05C63 The star-comb lemma is a standard tool in infinite graph theory, which states that for every infinite set $U$ of vertices in a connected graph $G$ there exists either a subdivided infinite star in $G$ with all leaves in $U$, or an infinite comb in $G$ with all teeth in $U$. In this paper, we elaborate a counterpart of the star-comb lemma for directed graphs. More precisely, we prove that for every infinite set $U$ of vertices in a strongly connected directed graph $D$, there exists a strongly connected butterfly minor of $D$ with infinitely many teeth in $U$ that is either shaped by a star or shaped by a comb, or is a chain of triangles. |
| title | A star-comb lemma for infinite digraphs |
| topic | Combinatorics 05C20, 05C40, 05C63 |
| url | https://arxiv.org/abs/2406.04877 |