Monochromatic reachability in arc-colored digraphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

An arc-colouring of a finite digraph $D=(V,A)$ with $k$ colours is a map $c:A\to\{1,\ldots,k\}$. A stable set contains no two vertices joined by an arc in either direction. A directed path is monochromatic if all its arcs have the same colour; a length-zero path allows a vertex already in the target set to reach itself.

Statement recorded in the supplied source.

For each positive integer $k$, is there a positive integer $f(k)$ such that every finite $k$-arc-coloured digraph $D$ admits stable sets $S_1,\ldots,S_{f(k)}$ with the following property? Writing $S=\bigcup_{j=1}^{f(k)}S_j$, every vertex of $D$ has a monochromatic directed path to some vertex of $S$. [S2]

Short English statement

Can a bounded number of stable sets, depending only on the number of arc colours, receive a monochromatic directed path from every vertex of any finite digraph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3275 (OPG-60028). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Monochromatic reachability in arc-colored digraphs, node 60028, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/monochromatoc_reachability_in_arc_colored_digraphs.