Erdős's bounded monochromatic reachability conjecture

From papers

Let kk be a positive integer. A kk-edge-coloured finite tournament is a finite tournament whose edges are assigned one of kk colours, and a set SV(T)S\subseteq V(T) is reachable from a vertex by a monochromatic path if some monochromatic directed path from that vertex ends in a vertex of SS. Erdős's conjecture. For every positive integer kk there is a least positive integer f(k)f(k) such that every kk-edge-coloured finite tournament admits a subset SV(T)S\subseteq V(T) of size at most f(k)f(k) such that SS is reachable from every vertex by a monochromatic path. It is known that f(1)=f(2)=1f(1)=f(2)=1 and that f(3)3f(3)\geq 3, but no constant upper bound for f(3)f(3) is known; Erdős conjectured that f(3)=3f(3)=3.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Kristóf Bérczi and Attila Joó, “King-serf duo by monochromatic paths in k-edge-coloured tournaments”, arXiv:1705.00896 (2017).

Solutions 0

No solutions have been posted yet.