Jackson–Thomassen conjecture on strong orientations of digraphs

Less than 1 year old · traced to

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 k−1k-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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.