$P_k$-freeness implies small dichromatic number

Krzysztof Choromanski

We propose a purely combinatorial quadratic time algorithm that for any $n$-vertex $P_k$-free tournament $T$, where $P_k$ is a directed path of length $k$, finds in $T$ a trans…