Orientation conjecture of Nash-Williams
From Egres Open
Any 2k-edge-connected (possibly infinite) multigraph admits a k-edge-connected orientation.
Remarks
The conjecture is formulated by Nash-Williams who also proved the restriction of it to finite multigraphs; this known as Nash-Williams' weak orientation theorem. See Nash-Williams' strong orientation theorem for the strong version of the theorem. The first (and so far the only) breakthrough for infinite graphs is due to C. Thomassen. He showed that a 8k-edge-connected infinite multigraph admits a k-edge-connected orientation [1]. The conjecture is implied by its own restriction to countably infinite, locally finite multigraphs hence it is essentially a countable problem.
References
- ↑ C. Thomassen, Orientations of infinite graphs with prescribed edge-connectivity, Combinatorica (2014): 1-21. DOI link, author link