Thomassen's orientation conjecture for highly connected graphs
Thomassen's orientation conjecture for highly connected graphs
A graph is -connected if it remains connected after the deletion of any set of at most vertices. An orientation of is -strong if its corresponding digraph remains strongly connected after the deletion of any set of at most vertices. Thomassen's conjecture. There exists an integer function such that every -connected graph has a -strong orientation. This conjecture was proved by Garamvölgyi, Jordan, Király and Villányi, who showed that one may take ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.