Thomassen's conjecture on good vertex pairs in arc-strong digraphs
Let be a digraph. It is -arc-strong if remains strong for every subset of size at most . An out-branching of is a spanning oriented tree in which every vertex except its root has in-degree one, and an in-branching is a spanning oriented tree in which every vertex except its root has out-degree one. A good -pair is a pair of arc-disjoint out-branching and in-branching rooted at and , respectively.
Thomassen's conjecture. There exists an integer such that every -arc-strong digraph has a good -pair for every choice of .
This conjecture asks for a uniform arc-connectivity condition guaranteeing compatible branchings with arbitrary prescribed roots. The source gives no resolution, so the conjecture remains open.
References
Primary source
Jiangdong Ai, Yiming Hao, Zhaoxiang Li and Qi Shao, “Arc-disjoint in- and out-branchings in semicomplete split digraphs”, arXiv:2410.12575 (2024).
Additional references
7 papers in this index state this conjecture (2020–2024). The statement above is taken from the most recent of them; the others are arXiv:2309.06904, arXiv:2302.08283, arXiv:2302.06177, arXiv:2206.12092, arXiv:2012.03742, arXiv:2007.02834.
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
No solutions have been posted yet.