Jackson–Thomassen conjecture

For every integer k≥1k\ge 1, every 2k2k-strong digraph DD has a spanning subdigraph HH such that HH is oriented and kk-strong; equivalently, V(H)=V(D)V(H)=V(D), A(H)⊆A(D)A(H)\subseteq A(D), HH contains no pair of oppositely directed arcs, and deleting fewer than kk vertices from HH leaves a strongly connected digraph.

References

Primary source

arXiv

Additional references

Progress summary

Refreshed
Claimed progress

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 2k2k-strong digraph has a spanning kk-strong oriented subdigraph. It is known for k=1k=1, but remains open for general digraphs already at k=2k=2.

September 2026 partial results

  • Bang-Jensen and Wei report sharp sufficient degree conditions, including δ0(D)≥⌊(n+k−1)/2⌋\delta^0(D)\ge\lfloor(n+k-1)/2\rfloor for fixed kk and sufficiently large nn, plus an extension to k≤αnk\le\alpha n with α<0.094882…\alpha<0.094882\ldots.
  • 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): k=1k=1 and several structured or dense cases are known, but the general Jackson–Thomassen conjecture remains open, including general k=2k=2.

Sources

Solutions 0

No solutions have been posted yet.