$P_k$-freeness implies small dichromatic number

Abstract

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 transitive subset of order $n^{\frac{c}{k\log (k{)}^2}}$. As a byproduct of our method, we obtain subcubic $O(n^{1-\frac{c}{k\log (k{)}^2}})$-approximation algorithm for the optimal acyclic coloring problem on $P_k$-free tournaments. Our results are tight up to the $\log (k)$-factor in the following sense: there exist infinite families of $P_k$-free tournaments with largest transitive subsets of order at most $n^{\frac{c\log (k)}{k}}$. As a corollary, we give tight asymptotic results regarding the so-called \textit{Erdős-Hajnal coefficients} of directed paths. These are some of the first asymptotic results on these coefficients for infinite families of prime graphs.