The Nash-Williams orientation theorem for graphs with countably many ends
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910548942127104 |
|---|---|
| author | Assem, Amena Koloschin, Marcel Pitz, Max |
| author_facet | Assem, Amena Koloschin, Marcel Pitz, Max |
| contents | Nash-Williams proved in 1960 that a finite graph admits a $k$-arc-connected orientation if and only if it is $2k$-edge-connected, and conjectured that the same result should hold for all infinite graphs, too.
Progress on Nash-Williams's problem was made by C. Thomassen, who proved in 2016 that all $8k$-edge-connected infinite graphs admit a $k$-arc connected orientation, and by the first author, who recently showed that edge-connectivity of $4k$ suffices for locally-finite, 1-ended graphs.
In the present article, we establish the optimal bound $2k$ in Nash-Williams's conjecture for all locally finite graphs with countably many ends. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_03601 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Nash-Williams orientation theorem for graphs with countably many ends Assem, Amena Koloschin, Marcel Pitz, Max Combinatorics 05C20, 05C40, 05C63 Nash-Williams proved in 1960 that a finite graph admits a $k$-arc-connected orientation if and only if it is $2k$-edge-connected, and conjectured that the same result should hold for all infinite graphs, too. Progress on Nash-Williams's problem was made by C. Thomassen, who proved in 2016 that all $8k$-edge-connected infinite graphs admit a $k$-arc connected orientation, and by the first author, who recently showed that edge-connectivity of $4k$ suffices for locally-finite, 1-ended graphs. In the present article, we establish the optimal bound $2k$ in Nash-Williams's conjecture for all locally finite graphs with countably many ends. |
| title | The Nash-Williams orientation theorem for graphs with countably many ends |
| topic | Combinatorics 05C20, 05C40, 05C63 |
| url | https://arxiv.org/abs/2310.03601 |