Every tournament of dichromatic number $10k^2$ has a vertex whose out-neighborhood has dichromatic number more than $k$

Abstract

The dichromatic number of a tournament is the minimum number of colors needed to color the vertices so that no directed cycle is monochromatic. Nguyen, Scott, and Seymour (2025) asked whether every tournament with dichromatic number $2k$ has a vertex whose out-neighborhood induces a subtournament of dichromatic number at least $k$. We answer their question negatively by finding an example with dichromatic number $\Omega (k^2)$. Furthermore, this quadratic bound is tight up to a constant factor; we show that for every integer $k\ge 1$, every tournament of dichromatic number $\Omega (k^2)$ contains a vertex whose out-neighborhood induces a subtournament of dichromatic number more than $k$. This improves the previous best bound $\mathcal{O}(k^2\log k)$ due to Colinot and Newman (2026). To show this, we prove that every tournament of fractional dichromatic number $c$ has a dominating set of size at most $5c-1$. The proof uses Brouwer's fixed point theorem.

arXiv comment7 pages