Problem of the month June 2010

The problem for June is the longstanding open problem on the 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?

The analogous result for k-edge-connected orientations is fairly easy and has far-reaching generalizations, for example Nash-Williams' strong orientation theorem. Therefore it is striking how few partial results are known for the node-connected problem, even for k=2. The rooted version is also open and interesting.

The problem page lists some known special cases and sufficient conditions. Please visit the discussion page of the problem if you have any observations, ideas or questions!