Orientation conjecture of Nash-Williams

From Egres Open
Jump to: navigation, search

Any [math] 2k [/math]-edge-connected (possibly infinite) multigraph admits a [math] k [/math]-edge-connected orientation.


Remarks

The conjecture is formulated by Nash-Williams who also proved the restriction of it to finite multigraphs; see Nash-Williams' strong orientation theorem. The first (and so far the only) breakthrough is due to C. Thomassen. He showed that a [math] 8k [/math]-edge-connected infinite multigraph admits a [math] k [/math]-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

  1. C. Thomassen, Orientations of infinite graphs with prescribed edge-connectivity, Combinatorica (2014): 1-21. DOI link, author link