Jackson–Thomassen conjecture on strong orientations of digraphs
Jackson–Thomassen conjecture on strong orientations of digraphs
Let be a digraph. It is -strong if it has at least vertices and remains strongly connected after the deletion of any subset of vertices. An oriented subdigraph is obtained by retaining exactly one arc from every directed -cycle of .
Jackson–Thomassen conjecture. Every -strong digraph has a spanning -strong oriented subdigraph.
For , 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 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
Sign in to submit a solution.
No solutions have been posted yet.