Thomassen's conjecture on good vertex pairs in arc-strong digraphs

About 6 years old · traced to

Let D=(V,A)D=(V,A) be a digraph. It is kk-arc-strong if D∖A′D\setminus A^{\prime} remains strong for every subset A′⊆A(D)A^{\prime}\subseteq A(D) of size at most k−1k-1. An out-branching of DD 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 (u,v)(u,v)-pair is a pair of arc-disjoint out-branching and in-branching rooted at uu and vv, respectively.

Thomassen's conjecture. There exists an integer KK such that every KK-arc-strong digraph D=(V,A)D=(V,A) has a good (u,v)(u,v)-pair for every choice of u,v∈Vu,v\in V.

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

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.