Thomassen's orientation conjecture for highly connected graphs

A graph G=(V,E)G=(V,E) is kk-connected if it remains connected after the deletion of any set of at most k1k-1 vertices. An orientation of GG is kk-strong if its corresponding digraph remains strongly connected after the deletion of any set of at most k1k-1 vertices. Thomassen's conjecture. There exists an integer function g(k)g(k) such that every g(k)g(k)-connected graph has a kk-strong orientation. This conjecture was proved by Garamvölgyi, Jordan, Király and Villányi, who showed that one may take g(k)320k2g(k)320k^2; it is therefore solved.

Sources & referencesView supporting material

Primary source

Jia Zhou, Jørgen Bang-Jensen, Tong Zhou and Jin Yan, “Highly connected spanning oriented subdigraphs in generalizations of semicomplete digraphs”, arXiv:2607.17150 (2026).

Additional references

24 papers in this index state this conjecture (2008–2026). The statement above is taken from the most recent of them; the others are arXiv:2605.02543, arXiv:2401.12670, arXiv:2206.00561, arXiv:2202.09253, arXiv:2201.13115, arXiv:2112.07539, arXiv:2011.11605, arXiv:2008.09783, arXiv:2004.00035, arXiv:1907.07219, arXiv:1907.08029, arXiv:1904.03818, and 11 more.

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.