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

@misc{kim2026every,
  title = {{Every tournament of dichromatic number $10 k^2$ has a vertex whose out-neighborhood has dichromatic number more than $k$}},
  author = {Seokbeom Kim and Sang-il Oum},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.29043},
  eprint = {2610.29043},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.29043},
}

TY  - UNPB
TI  - Every tournament of dichromatic number 10 k^2 has a vertex whose out-neighborhood has dichromatic number more than k
AU  - Seokbeom Kim
AU  - Sang-il Oum
PY  - 2026
DA  - 2026/10/21
PB  - arXiv
DO  - 10.48550/arxiv.2610.29043
UR  - https://arxiv.org/abs/2610.29043
AB  - 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 Ω(k^2). Furthermore, this quadratic bound is tight up to a constant factor; we show that for every integer k ≥ 1, every tournament of dichromatic number Ω(k^2) contains a vertex whose out-neighborhood induces a subtournament of dichromatic number more than k. This improves the previous best bound 𝒪(k^2log 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.
ER  -