Jackson–Thomassen conjecture on strong orientations of digraphs

From papers

Let D=(V,A)D=(V,A) be a digraph. It is kk-strong if it has at least k+1k+1 vertices and remains strongly connected after the deletion of any subset of k1k-1 vertices. An oriented subdigraph is obtained by retaining exactly one arc from every directed 22-cycle of DD.

Jackson–Thomassen conjecture. Every 2k2k-strong digraph has a spanning kk-strong oriented subdigraph.

For k=1k=1, this follows from a result of Boesch and Tindell on strong orientations of mixed graphs, and the conjecture is known for symmetric digraphs by Thomassen. It remains open even for k=2k=2 in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Tong Zhou, Jørgen Bang-Jensen, Jia Zhou and Jin Yan, “K-Arc-Strong Orientations Of Semicomplete Digraphs”, arXiv:2607.17116 (2026).

Solutions 0

No solutions have been posted yet.