Bang-Jensen–Yeo arc-partition conjecture for highly arc-connected digraphs

Let D=(V,A)D=(V,A) be a digraph. An arc-partition is a partition of its arc set into two parts, A=A1A2A=A_1\cup A_2, and a subdigraph is spanning and strong if it has vertex set VV and is strongly connected.

Bang-Jensen–Yeo's conjecture. There exists an integer KK such that every KK-arc-strong digraph D=(V,A)D=(V,A) has an arc-partition

A=A1A2A=A_1\cup A_2

such that each of the subdigraphs D1=(V,A1)D_1=(V,A_1) and D2=(V,A2)D_2=(V,A_2) is spanning and strong.

This conjecture would imply Thomassen's good-pair conjecture by decomposing a sufficiently arc-strong digraph into two spanning strong subdigraphs. The source states that it is open; in particular, the minimum such KK is unknown.

Sources & referencesView supporting material

Primary source

Joergen Bang-Jensen and Yun Wang, “Arc-disjoint out-branchings and in-branchings in semicomplete digraphs”, arXiv:2302.06177 (2023).

Additional references

4 papers in this index state this conjecture (2018–2023). The statement above is taken from the most recent of them; the others are arXiv:2206.12092, arXiv:1812.08809, arXiv:1808.02740.

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.