χ-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 open medium confidence

No paper has been found that resolves Question 3.2 either positively or negatively. The closely related questions about t-chordal digraphs (all induced directed cycles of the same length t) have been answered negatively — for each t ≥ 3 there exist t-chordal digraphs with clique number at most 3 and arbitrarily large dichromatic number (arXiv:2203.15575, arXiv:2202.01006) — but these results concern digraphs where induced cycles are restricted to a fixed length, not digraphs where all odd-length induced directed cycles are absent. The distinction is material: banning every odd-length induced directed cycle is a much stronger condition, and the question of whether it forces χ⃗(D) ≤ f(ω(D)) remains open to the best of available search results.

Cited literature (2)

partial Digraphs with all induced directed cycles of the same length are not $\vec{\chi}$-bounded (2022)

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

For each t ≥ 3, there exist t-chordal digraphs (all induced directed cycles have length t) with clique number at most 3 and arbitrarily large dichromatic number, showing that t-chordal digraph classes are not χ⃗-bounded; this is a related but distinct condition from the one in Question 3.2.
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. The construction in arXiv:2201.08204 itself is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5 (i.e., it avoids odd cycles of length ≥ 5, but may have odd cycles of length 3). Question 3.2 asks whether banning ALL odd-length induced directed cycles (including length 3) suffices to bound the dichromatic number. No resolution of this stronger question was found in the indexed literature within the cap of 5 web calls.

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

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.

Also stated in

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