On Frank's conjecture on k-connected orientations

2012/12/17 by de Gevigney, Olivier Durand · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1212.4086

Abstract

We disprove a conjecture of Frank stating that each weakly 2k-connected has a k-vertex-connected orientation. For k at least 3, we also prove that the problem of deciding whether a graph has a k-vertex-connected orientation is NP-complete.

Cited by

• Color-avoiding connected colorings and orientations
• Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach

Related

• On orientations preserving edge-connectivity in infinite graphs
• Connectivity of orientations of 3-edge-connected graphs
• A note on 2-vertex-connected orientations
• Orientations of infinite graphs
• Orientations of graphs with at most one directed path between every pair of vertices