Rainbow reachability and the multi-label core obstruction

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple loopless digraph with $V\ne\varnothing$, and choose subsets $E_1,\ldots,E_k\subseteq E$ for some $k\ge1$. These subsets need not be disjoint. An arc $e$ has the available labels $S_e=\{i:e\in E_i\}$. A directed path or directed cycle is rainbow if one can assign to each of its arcs a label in $S_e$ so that all assigned labels are distinct. Labels are chosen for that occurrence of the path or cycle; they need not increase along it. An arc having no labels cannot be used in a rainbow structure.

Set $G_i=(V,E_i)$, and let $d_i^+(v)$ be its outdegree at $v$. Let $R(v)$ be the set of vertices other than $v$ reachable from $v$ by a positive-length rainbow directed path. Paths have distinct vertices, while cycles have distinct vertices apart from their common start and end. The proposed alternative is \[ \text{there exists a rainbow directed cycle,} \quad\text{or}\quad \exists v\in V:\ |R(v)|\ge\sum_{i=1}^k d_i^+(v). \] The sum counts a multi-labelled outgoing arc once for each of its labels; reachable vertices are counted only once. This distinction is part of the force of the assertion. There is no restriction on opposite arcs, and no global assignment of a single color to every arc is assumed.

Short English statement

Must a directed graph with overlapping edge-label sets have either a rainbow cycle or a vertex with sufficiently large rainbow reachability?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001036 (AIM-COMBINATORICS-0161), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6. Original workshop question underlying AIM-COMBINATORICS-0161. https://aimath.org/WWN/caccetta/caccetta.pdf.