Jackson–Thomassen conjecture
For every integer , every -strong digraph has a spanning subdigraph such that is oriented and -strong; equivalently, , , contains no pair of oppositely directed arcs, and deleting fewer than vertices from leaves a strongly connected digraph.
References
Primary source
Additional references
- Degree conditions for k-strong orientations of digraphs — arXiv — Jørgen Bang-Jensen, Shuo Wei
Progress summary
New work establishes sharp degree-based cases, but the conjecture remains open for arbitrary directed graphs.
Posed by Jackson and Thomassen in 1989, the conjecture says that every -strong digraph has a spanning -strong oriented subdigraph. It is known for , but remains open for general digraphs already at .
September 2026 partial results
- Bang-Jensen and Wei report sharp sufficient degree conditions, including for fixed and sufficiently large , plus an extension to with .
- Other September papers establish the conjectured conclusion for extended semicomplete, semicomplete split, and related composition classes, but not arbitrary digraphs.
- A separate result settles the analogous arc-connectivity statement, not the vertex-connectivity conjecture.
Current status (as of September 2026): and several structured or dense cases are known, but the general Jackson–Thomassen conjecture remains open, including general .
Solutions 0
No solutions have been posted yet.