Home » Subject » Graph Theory » Directed Graphs » Tournaments

Monochromatic reachability in edge-colored tournaments (Solved)

Importance: High ✭✭✭
Author(s): Erdos, Paul
Subject: Graph Theory
» Directed Graphs
» » Tournaments
Keywords: digraph
edge-coloring
tournament
Recomm. for undergrads: no
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
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 $?

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


* indicates original appearance(s) of problem.
add new comment