Monochromatic reachability in arc-colored digraphs

Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: fhavet
on: April 4th, 2017

\begin{conjecture} For every $k$, there exists an integer $f(k)$ such that if $D$ is a digraph whose arcs are colored with $k$ colors, then $D$ has a $S$ set which is the union of $f(k)$ stables sets so that every vertex has a monochromatic path to some vertex in $S$. \end{conjecture}

In the particular case of tournaments (and more generally when the stabilty number of $D$ is bounded), it has been proved by Bousquet, Lochet, and Thomassé [BLT].


[BLT] Nicolas Bousquet, William Lochet, Stéphan Thomassé: \arxiv[A proof of the Erdős-Sands-Sauer-Woodrow conjecture]{math.CO/1703.08123},

[SSW] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs. Journal of Combinatorial Theory, Series B, 33, (1982), 271--275.

* indicates original appearance(s) of problem.