High chromatic number forcing high degeneracy out-neighbourhood

Question 10 · arXiv:2305.15585

arXiv Question 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

Question 10 of arXiv:2305.15585 asks whether high chromatic number forces some out-neighbourhood to have high degeneracy; the authors explicitly state they have been unable to determine this. The paper establishes a positive analogue for the degeneracy-to-degeneracy setting (Theorem 6: high degeneracy forces a two-vertex out-neighbourhood with high degeneracy), but the chromatic-number version for a single vertex remains open. No follow-up paper resolving the question was found in a search covering literature through May 2026.

Reviewer notes. No follow-up found after a 5-call web search. The paper (published in JCTB 2024) itself poses Question 10 as genuinely open, distinguishing it from the degeneracy-to-degeneracy case which the authors resolve positively. The Barbados 2025 open-problems PDF was inaccessible (binary/compressed), and the related survey arXiv:2306.02364 focuses on tournament colouring structure rather than this specific question.

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

Question. Does there exist, for each integer $d$, an integer $\chi$ such that for every graph $G$ with $\chi(G)\geqslant\chi$ and every tournament $T$ on the same vertex set, there is a vertex $v$ for which $G[N^{+}_{T}(v)]$ has degeneracy at least $d$?

Context

In the closing remarks the authors note they have been unable to determine whether high chromatic number forces an out-neighbourhood with high degeneracy. The paper's disproof of Conjecture 1 shows chromatic number is not preserved, but degeneracy is a weaker measure and may behave differently.

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