![](/files/happy5.png)
Monochromatic reachability in arc-colored digraphs
Conjecture For every
, there exists an integer
such that if
is a digraph whose arcs are colored with
colors, then
has a
set which is the union of
stables sets so that every vertex has a monochromatic path to some vertex in
.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ f(k) $](/files/tex/e055b3867e7cb3cc4b2f50739eedda7657999214.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ S $](/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png)
![$ f(k) $](/files/tex/e055b3867e7cb3cc4b2f50739eedda7657999214.png)
![$ S $](/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png)
In the particular case of tournaments (and more generally when the stabilty number of is bounded), it has been proved by Bousquet, Lochet, and Thomassé [BLT].
Bibliography
[BLT] Nicolas Bousquet, William Lochet, Stéphan Thomassé: A proof of the Erdős-Sands-Sauer-Woodrow conjecture,
[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.