Highly element-connected orientation
Is it true that if an undirected graph G with terminal set T is 2k-element-connected, then it has a k-element-connected orientation?
An analogous statement for rooted element-connectivity was proved by Király and Lau . A directed graph D with terminal set T is rooted k-element-connected from [math]r \in T[/math] if there are k element-disjoint paths from r to any other node in T. It is NP-complete to decide if a graph has a rooted k-element-connected orientation, but Király and Lau proved that if the graph is 2k-element-connected, then for any root [math]r \in T[/math] it has a rooted k-element-connected orientation.
Cheriyan and Zou  proved the conjecture for incidence graphs of projective planes, where the terminal set is one side of the bipartition. An important related result is the characterization of graphs having a 2-connected orientation by Thomassen , see also Characterization of graphs having a k-connected orientation.
- T. Király, L.C. Lau, Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, Journal of Combinatorial Theory B 98 (2008), 1233-1252. DOI link, EGRES Technical Report
- J. Cheriyan, C. Zou, On orienting graphs for connectivity: Projective planes and Halin graphs, Operations Research Letters 40 (2012), 337–341, DOI link
- C. Thomassen, Strongly 2-connected orientations of graphs, JCTB 110 (2015), 67-78, DOI link