Rainbow Arborescences Across Arc Partitions

Definitions and mathematical statement

For the following formulation, an out-arborescence on a finite vertex set $V$ is a set of arcs whose underlying undirected graph is a tree spanning $V$, with a root $r\in V$ such that every vertex is reachable from $r$ by a directed path. Equivalently, the root has indegree zero and every other vertex has indegree one. The source does not specify the orientation convention for arborescences; using in-arborescences throughout gives the corresponding formulation by reversing every arc.

For every positive integer $k$, let $G=(V,A)$ be a finite directed graph with $|V|=k+1$. Suppose that \[ A=F_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}F_k, \] where each $F_i$ is an arborescence on $V$ and $|F_i|=k$. Must there exist an arborescence $F^*\subseteq A$ on $V$ satisfying \[ |F^*\cap F_i|=1\qquad\text{for every }i\in\{1,\ldots,k\}? \] The roots of the given arborescences may differ, and the root of $F^*$ is not prescribed. Thus $F^*$ must select exactly one arc from each part of the partition. The source does not specify whether parallel arcs are permitted; the intended class of directed graphs requires confirmation. The positive-integer range expresses the nonempty family in the source; inclusion of $k=0$ would require conventions for an empty partition and the singleton arborescence.

Short English statement

If the arcs of a directed graph on $k+1$ vertices split into $k$ spanning arborescences, must one be able to select one arc from each to obtain another spanning arborescence? No common or prescribed root is assumed. The supplied record labels the problem partially solved; this draft does not independently verify that assessment.

Sources

• Local UnsolvedMath registry, permanent ID $30004008$, supplied complete source record; title: Rainbow Arborescences Across Arc Partitions; source problem code: catalogue entry. The record belongs to Oberwolfach Reports Open Problems and records proposed year 2018. No individual proposer is supplied.
• Supplied report citation: Combinatorial Optimization (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023. https://doi.org/10.4171/owr/2018/50. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference: Rainbow Arborescence Conjecture. https://arxiv.org/abs/2412.15457.
• Supplied literature reference: The Rainbow Arborescence Problem on Cycles. https://arxiv.org/abs/2511.04953.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem partially solved and states that the rainbow-arborescence existence conjecture remains open, fixed-root existence testing is NP-complete, and the conjecture is proved in several cases, including cyclic underlying graphs and common roots. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. Its status and cited claims require independent verification.
• The supplied statement status is corrected_verified; its accompanying explanation says that mathematical content was preserved while notation, typography, duplicate clauses, or omitted definitions were repaired for self-contained publication. This is a source-record label, not mathematical verification performed for this draft.