χ threshold for tournament out-neighbourhood 3-coloring

Conjecture 13 · arXiv:2305.15585

arXiv Conjecture high confidence— first stated 2023-12-04

Authors: António Girão, Kevin Hendrey, Freddie Illingworth, Florian Lehner, Lukas Michel, Michael Savery, Raphael Steiner

Status open high confidence

Conjecture 13 from arXiv:2305.15585 asks whether a function f(N)=o(log N) exists such that for every N-vertex graph G with \chi(G)\geq f(N) and every tournament T on the same vertex set, some vertex v satisfies \chi(G[N^+_T(v)])\geq 3. The paper itself (published in JCTB 168, 2024) establishes this only with a bound of \lceil\log_2(N)/\lfloor\chi/2-1\rfloor\rceil out-neighbourhoods rather than a single vertex. No follow-up paper resolving Conjecture 13 was found in the indexed literature as of May 2026.

Reviewer notes. No follow-up found. Conjecture 13 is presented as an open question in the closing remarks of the source paper. The paper was published as JCTB 168 (2024) 86-95. The related paper arXiv:2306.02364 (Nguyen, Scott, Seymour on tournament structure problems) does not appear to address this conjecture. The conjecture is recent (2023) and the absence of evidence of resolution supports high-confidence open status.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. There exists $f(N)$ satisfying $f(N)=o(\log N)$ such that for every $N$-vertex graph $G$ with $\chi(G)\geqslant f(N)$, and every tournament $T$ on the same vertex set, there is a vertex $v$ for which $\chi(G[N^{+}_{T}(v)])\geqslant 3$.

Context

Theorem 2 shows a collection of at most $\lceil\log_2(N)/\lfloor\chi/2-1\rfloor\rceil$ out-neighbourhoods suffices to force chromatic number at least 3; the authors ask whether $o(\log(N)/\chi)$ out-neighbourhoods (or even a single vertex) suffice when the chromatic number threshold itself grows with $N$ as $o(\log N)$.

Source paper

Chromatic number is not tournament-local
António Girão, Kevin Hendrey, Freddie Illingworth, Florian Lehner, Lukas Michel, Michael Savery, Raphael Steiner · 2023-12-04
https://arxiv.org/abs/2305.15585