On order-compatible paths in infinite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912955649490944 |
|---|---|
| author | Pitz, Max Real, Lucas Schaut, Roman |
| author_facet | Pitz, Max Real, Lucas Schaut, Roman |
| contents | Two $a{-}b$ paths in a graph $G$ are order-compatible if their common vertices occur in the same order when travelling from $a$ to $b$. Suppose a graph contains an infinite number $δ$ of edge-disjoint $a{-}b$ paths. G.A. Dirac asked whether there always exists a family of $δ$ edge-disjoint $a{-}b$ paths that are pairwise order-compatible. Confirming a conjecture by B. Zelinka, we show that this holds provided that the given $δ$ edge-disjoint $a{-}b$ paths have bounded length. Combining this with an earlier work of Zelinka, it follows that Dirac's question for an infinite cardinal $δ$ has an affirmative answer if and only if $δ$ has uncountable cofinality. As our second main result, we show that even when Dirac's question fails, it still holds that 'being connected by $δ$ edge-disjoint, pairwise order-compatible paths' is an equivalence relation for all values of $δ$. The most interesting case here is when $δ$ is countable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08454 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On order-compatible paths in infinite graphs Pitz, Max Real, Lucas Schaut, Roman Combinatorics 05C63, 05C40 Two $a{-}b$ paths in a graph $G$ are order-compatible if their common vertices occur in the same order when travelling from $a$ to $b$. Suppose a graph contains an infinite number $δ$ of edge-disjoint $a{-}b$ paths. G.A. Dirac asked whether there always exists a family of $δ$ edge-disjoint $a{-}b$ paths that are pairwise order-compatible. Confirming a conjecture by B. Zelinka, we show that this holds provided that the given $δ$ edge-disjoint $a{-}b$ paths have bounded length. Combining this with an earlier work of Zelinka, it follows that Dirac's question for an infinite cardinal $δ$ has an affirmative answer if and only if $δ$ has uncountable cofinality. As our second main result, we show that even when Dirac's question fails, it still holds that 'being connected by $δ$ edge-disjoint, pairwise order-compatible paths' is an equivalence relation for all values of $δ$. The most interesting case here is when $δ$ is countable. |
| title | On order-compatible paths in infinite graphs |
| topic | Combinatorics 05C63, 05C40 |
| url | https://arxiv.org/abs/2603.08454 |