On Frank's conjecture on k-connected orientations
classification
🧮 math.CO
cs.DM
keywords
conjecturefrankk-connectedk-vertex-connectedorientationdecidingdisprovegraph
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.