The Nash-Williams orientation theorem for graphs with countably many ends
Nash-Williams proved in 1960 that a finite graph admits a k -arc-connected orientation if and only if it is 2 k -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 8 k -edge-connected infinite graphs admit a k -arc connected orientation, and by the first author, who recently showed that edge-connectivity of 4 k suffices for locally-finite, 1-ended graphs. In the present article, we establish the optimal bound 2 k in Nash-Williams’s conjecture for all locally finite graphs with countably many ends.
Authors
- Marcel Koloschin
- Max Pitz (ORCID: https://orcid.org/0000-0001-8961-6132)
- Amena Assem
Institutions
- University of Waterloo (CA)
- Universität Hamburg (DE)
Publication Details
- Journal
- European Journal of Combinatorics
- Published
- 2024-08-22
- DOI
- https://doi.org/10.1016/j.ejc.2024.104043
- Citations
- 2
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.72