Equivalent Rainbow Arborescence Conjecture for at least n−1n-1 colors

About 2 years old · traced to

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

Equivalent Rainbow Arborescence Conjecture. If k≥n−1k \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 k≠n−1k \ne n-1. It remains open.

References

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.