χ-boundedness for odd-cycle-free digraphs

Question 3.2 · arXiv:2201.08204

arXiv Question high confidence— first stated 2022-09-15

Authors: Alvaro Carbonero, Patrick Hompe, Benjamin Moore, Sophie Spirkl

Status disproved high confidence

The answer is negative: the t=4 case of the cited fixed-length-cycle theorem gives bounded-clique digraphs with unbounded dichromatic number and no odd induced directed cycle.

Cited literature (2)

counterexample Digraphs with all induced directed cycles of the same length are not dichromatically bounded (2022)

Carbonero, Hompe, Moore, Spirkl · The Electronic Journal of Combinatorics, v29i4p4 · arXiv:2203.15575

The answer is negative: the t=4 case of the cited fixed-length-cycle theorem gives bounded-clique digraphs with unbounded dichromatic number and no odd induced directed cycle.

Read the literature-status audit
partial Chordal directed graphs are not $\vec{\chi}$-bounded (2022)

Aboulker, Bousquet, de Verclos · The Electronic Journal of Combinatorics, v29i2p17 · arXiv:2202.01006

Digraphs with no transitive tournament on 3 vertices in which every induced directed cycle has length 3 can have arbitrarily large dichromatic number, negatively answering a related question from the same source paper but not Question 3.2 directly.

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This is a direct corollary of the theorem reported for arXiv:2203.15575, not a new proof of its construction.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Question. Is there a function $f : \mathbb{N} \to \mathbb{N}$ such that for every digraph $D$ with no induced directed cycle of odd length, we have $\vec{\chi}(D) \leq f(\omega(D))$?

Context

Motivated by Theorem 1.5, which shows that the digraph analogue of the Scott–Seymour theorem on odd holes fails, the authors ask whether banning all odd-length induced directed cycles forces the dichromatic number to be bounded by a function of the clique number.

Notes. The paper states that Questions 3.2 and 3.4 were subsequently answered in the negative by the same authors in arXiv:2203.15575.

Source paper

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
Alvaro Carbonero, Patrick Hompe, Benjamin Moore, Sophie Spirkl · 2022-09-15
https://arxiv.org/abs/2201.08204 PDF source