Characterization of graphs having a k-connected orientation
Is it true that a simple graph G has a k-connected orientation if and only if the deletion of any j<k nodes leaves a 2(k-j)-edge-connected graph?
For [math]k = 2[/math], the conjecture was proved by Carsten Thomassen . The general conjecture has been disproved by Olivier Durand de Gevigney . For [math]k \geq 3[/math], he showed that it is NP-complete to decide if a given graph has a k-connected orientation. By a slight modification of the proof, he could also show that the problem of deciding the existence of a rooted k-connected orientation is NP-complete if [math]k \geq 3[/math].
Gerards  observed that every 4-regular 4-edge-connected graph has a 2-connected orientation. Later Berg and Jordán  proved that the conjecture is true for k=2 in any Eulerian graph. A simpler proof for this case was found by Király and Szigeti . The conjecture was verified for Halin graphs by Cheriyan and Zou .
For general graphs even the k=2 case was open for a long time. A sufficient condition was found by Jordán : every 18-connected graph has a 2-connected orientation. This was recently improved to 14-connectivity by Cheriyan, Durand de Gevigney and Szigeti . The conjecture itself for k=2 was recently proved by Thomassen .
The property that the deletion of any j<k nodes leaves a 2(k-j)-edge-connected graph is a special case of [math](n,\lambda)[/math]-connectivity defined by Kaneko and Ota , and it can be checked in polynomial time.
The following local version of the conjecture follows from the results of Egawa, Kaneko and Matsumo :
Theorem. An undirected graph with two specified nodes s and t has an orientation in which [math]\kappa(s,t) \geq k[/math] and [math]\kappa(t,s) \geq k[/math] if and only if for every set X of j<k nodes distinct from s and t, G-X is 2(k-j)-edge-connected between s and t.
- C. Thomassen, Strongly 2-connected orientations of graphs, JCTB 110 (2015), 67-78, DOI link.
- O. Durand de Gevigney, On Frank's conjecture on k-connected orientations, arXiv link.
- A.M.H. Gerards, On 2-vertex connected orientations, manuscript, 1997.
- A. R. Berg, T. Jordán, Two-connected orientations of Eulerian graphs, Journal of Graph Theory 52 (2006),230-242. DOI link, EGRES Technical Report.
- Z. Király, Z. Szigeti, Simultaneous well-balanced orientations of graphs, DOI link.
- Z. Király, Z. Szigeti, Reliable Orientations of Eulerian Graphs, EGRES Technical Reprot no. 2006-01.
- J. Cheriyan, C. Zou, On orienting graphs for connectivity: Projective planes and Halin graphs, Operations Research Letters 40 (2012), 337–341, DOI link.
- T. Jordán, On the existence of k edge-disjoint 2-connected spanning subgraphs, DOI link, EGRES Technical Report.
- J. Cheriyan, O. Durand de Gevigney, Z. Szigeti, Packing of Rigid Spanning Subgraphs and Spanning Trees, arXiv link
- A. Kaneko, K. Ota, On minimally (n,λ)-connected graphs, Journal of Combinatorial Theory, Series B 80 (2000), 156-171. DOI link.
- Y. Egawa, A. Kaneko, M. Matsumoto, A mixed version of Menger's theorem, Combinatorica 11 (1991), 71-74.DOI link.