News

Rainbow arborescences

The famous Ryser – Brualdi – Stein conjecture asserts that every $n\times n$ Latin square contains a partial transversal of size $n-1$. Since its appearance, the conjecture has attracted significant interest, leading to several generalizations. One of the most notable extensions is to matroid intersection given by Aharoni, Kotlar, and Ziv, focusing on the existence of a common independent transversal of the common independent sets of two matroids. In our paper Rainbow Arborescence Conjecture, we study a special case of this setting, which states that any graph on $n$ vertices formed by the union of $n−1$ spanning arborescences contains an arborescence using exactly one arc from each. We prove that the computational problem of testing the existence of such an arborescence with a fixed root is NP-complete, verify the conjecture in several cases, and explore relaxed versions of the problem.