## King-serf duo by monochromatic paths in k-edge-coloured tournaments

### Abstract

An open conjecture of Erdos states that for every positive integer $k$ there is a (least) positive integer $f(k)$ so that whenever a tournament has its edges colored with $k$ colors, there exists a set $S$ of at most $f(k)$ vertices so that every vertex has a monochromatic path to some point in $S$. We consider a related question and show that for every (finite or infinite) cardinal $\kappa>0$ there is a cardinal $\lambda_\kappa$ such that in every $\kappa$-edge-coloured tournament there exist disjoint vertex sets $K,S$ with total size at most $\lambda_\kappa$ so that every vertex $v$ has a monochromatic path of length at most two from $K$ to $v$ or from $v$ to $S$.

Bibtex entry:

@techreport{egres-16-08,
AUTHOR = {B{\'e}rczi, Krist{\'o}f and Jo{\'o}, Attila},
TITLE = {King-serf duo by monochromatic paths in k-edge-coloured tournaments},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-08}
}

Last modification: 5.12.2018. Please email your comments to Tamás Király!