Cycle in out-neighbourhood for high-χ graphs

Conjecture 11 · 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 11 from arXiv:2305.15585 asks whether sufficiently large chromatic number of a graph G forces, for every tournament T on the same vertex set, some out-neighbourhood G[N+_T(v)] to contain a cycle; this is the d=2 (weakest non-trivial) case of the degeneracy Question 10 from the same paper. The source paper was published in Journal of Combinatorial Theory, Series B 168 (2024), pp. 86–95, but no subsequent work resolving Conjecture 11 was identified through web searches covering the period up to May 2026.

Reviewer notes. No follow-up paper addressing Conjecture 11 was found. The conjecture is the d=2 case of the degeneracy Question 10; the paper's main results concern the chromatic-number version (disproving Scott–Seymour), while Conjecture 11 targets the much weaker cycle-containment requirement. The paper notes that bipartite (1-degenerate) graphs appear in their counterexamples, making d=2 the first open degeneracy case. Searches also retrieved arXiv:2306.02364 (Nguyen–Seymour survey on tournament structure) and arXiv:2503.20045 (Koerts–Moore–Spirkl on cycle orientations in digraphs), neither of which was confirmed to address this specific conjecture.

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

Conjecture. For every graph $G$ with sufficiently large chromatic number, and every tournament $T$ on the same vertex set, there exists a vertex $v$ such that $G[N^{+}_{T}(v)]$ contains a cycle.

Context

The authors suspect that the case $d=2$ of Question 10 is true, i.e., high chromatic number should force some out-neighbourhood to contain a cycle. This is the weakest non-trivial instance of the degeneracy question, since bipartite graphs (which arise in their counterexamples) are acyclic-free but 1-degenerate.

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