Heroic triple with oriented forest and K_k

Conjecture 4.4 · arXiv:2009.13319

arXiv Conjecture medium confidence— first stated 2020-09-28

Authors: Pierre Aboulker, Pierre Charbit, Reza Naserasr

Status partial medium confidence

Conjecture 4.4 — that $\{\overleftrightarrow{K_2}, K_k, F\}$ is heroic for every oriented forest $F$ and every integer $k$ — remains open in full generality. Two follow-up papers from the curated corpus establish special cases: arXiv:2103.07886 handles $F = S_2^+$ (oriented star with two out-edges) and arXiv:2212.02272 handles $F = \overrightarrow{P}_6$ with the clique constraint $\omega \le 2$ (triangle-free). A separate paper (arXiv:2202.13306) is noted to disprove a conjecture of Aboulker, Charbit, and Naserasr in the context of heroes in oriented complete multipartite graphs, but its abstract does not specify which conjecture from the source paper, so it is not attributed to Conjecture 4.4 here.

Cited literature (2)

partial Decomposing and colouring some locally semicomplete digraphs (2022)

Pierre Aboulker, Guillaume Aubian, Pierre Charbit · arXiv preprint · arXiv:2103.07886

Proves the conjecture for the special case $F = S_2^+$: every locally out-transitive oriented graph has dichromatic number at most 2 (Theorem 3.2), which corresponds to $\{\overleftrightarrow{K_2}, K_k, S_2^+\}$ being heroic.
partial (P6, triangle)-free digraphs have bounded dichromatic number (2023)

Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Stéphan Thomassé · arXiv preprint · arXiv:2212.02272

Proves the conjecture for the special case $F = \overrightarrow{P}_6$ with $k = 3$ (triangle-free digraphs): every $\overrightarrow{P}_6$-free digraph with $\omega(D) \le 2$ has dichromatic number at most 382 (Theorem 1.3).

Reviewer notes. arXiv:2202.13306 ('Heroes in oriented complete multipartite graphs', Aboulker et al., 2022) was found in search results and its abstract states it disproves a conjecture of Aboulker, Charbit, and Naserasr; however, the abstract specifies the result is about heroes in oriented complete multipartite graphs — likely a different structural conjecture from the same source paper — and the abstract does not name Conjecture 4.4 specifically. It is therefore excluded from since_posted pending full-text verification. The Electronic Journal of Combinatorics paper 'Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of P4' appeared in search results and may constitute additional partial progress (F = oriented P4), but could not be verified within the 5-call budget.

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

Conjecture. Given an oriented forest $F$ and for every integer $k$, $\{\overleftrightarrow{K_2}, K_k, F\}$ is heroic.

Context

This conjecture is equivalent to the special case of Conjecture 4.2 where $H = TT_k$ is a transitive tournament, since every tournament on at least $2k$ vertices contains $TT_k$ as an induced subdigraph. It generalises the heroic-set result for $\{\overleftrightarrow{K_2}, K_k, P^+(3)\}$ proved in Theorem 4.3, where $K_k$ denotes the digraph on $k$ vertices with no arc.

Notes. PDF source — the raw text reads 'for every integer l' but uses $K_k$ in the set; the variable $l$ is likely a PDF extraction artifact for $k$. Here $K_k$ denotes the independent set (edgeless digraph) on $k$ vertices, as per the paper's notation.

Source paper

Extension of Gyarfas-Sumner conjecture to digraphs
Pierre Aboulker, Pierre Charbit, Reza Naserasr · 2020-09-28
https://arxiv.org/abs/2009.13319 PDF source