# Monochromatic reachability in edge-colored tournaments (Solved)

 Importance: High ✭✭✭
 Author(s): Erdos, Paul
 Subject: Graph Theory » Directed Graphs » » Tournaments
 Keywords: digraph edge-coloring tournament
 Posted by: mdevos on: July 9th, 2008
 Solved by: Bousquet, Lochet, and Thomassé. A proof of the Erdős-Sands-Sauer-Woodrow conjecture https://arxiv.org/abs/1703.08123

\begin{problem} For every $n$, is there a (least) positive integer $f(n)$ so that whenever a tournament has its edges colored with $n$ colors, there exists a set $S$ of at most $f(n)$ vertices so that every vertex has a monochromatic path to some point in $S$? \end{problem}

This problem first appears in print in a lovely paper of Sands, Sauer, and Woodrow [SSW], where they prove that $f(2) = 1$. Actually, they prove a much stronger theorem. They show that for every 2-edge-colored digraph $G$ (even infinite) there exists an independent set $S \subseteq V(G)$ so that every vertex has a monochromatic path to some point in $S$.

It is open whether $f(k)$ is finite for every $k \ge 3$. The smallest open case, $k=3$, is already quite interesting; In [SSW] the authors ask if $f(3) = 3$.

## Bibliography

*[SSW] B. Sands, N. Sauer, R. Woodrow, On monochromatic paths in edge-coloured digraphs. J. Combin. Theory Ser. B 33 (1982), no. 3, 271--275. \MRhref{MR0693367}.

* indicates original appearance(s) of problem.