Equivalent Rainbow Arborescence Conjecture for at least n1n-1 colors

Let GG be a digraph on a vertex set VV of size n2n \ge 2, formed as the disjoint union of kk spanning arborescences A1,,AkA_1,\ldots,A_k. A subgraph BB is rainbow if BAi1|B \cap A_i| \le 1 for every color ii.

Equivalent Rainbow Arborescence Conjecture. If kn1k \ge n-1, then the disjoint union GG of kk spanning arborescences has a rainbow spanning arborescence BB.

The paper states that this formulation is equivalent to Yokoi's conjecture and may be easier to use when kn1k \ne n-1. It remains open.

Sources & referencesView supporting material

Primary source

Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi and Yu Yokoi, “Rainbow Arborescence Conjecture”, arXiv:2412.15457 (2025).

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.