Home » Subject » Graph Theory » Directed Graphs

Monochromatic reachability in arc-colored digraphs

Importance: High ✭✭✭
Author(s): Sands, Bill
Sauer, Norbert W.
Woodrow, Robert E.
Subject: Graph Theory
» Directed Graphs
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: April 4th, 2017
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 $.

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].

Related problems

Monochromatic reachability in edge-colored tournaments
Monochromatic reachability or rainbow triangles

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.
add new comment