Heroic sets for bounded dichromatic number

Status partial high confidence

Problem 1.2 asks for a full characterization of all finite sets of digraphs that are heroic (i.e., whose avoidance guarantees bounded dichromatic number); this characterization remains open. Partial progress includes: locally out-transitive oriented graphs shown to have dichromatic number at most 2 (arXiv:2103.07886); (P6, triangle)-free oriented graphs shown to have dichromatic number at most 382 (arXiv:2212.02272); heroes in oriented complete multipartite graphs nearly fully characterized (arXiv:2202.13306). A 2026 preprint (arXiv:2602.08736) disproves the related conjecture that {oriented star forest, hero} always forms a heroic pair, by constructing (Claw, C3)-free orientations of rook graphs with unbounded dichromatic number.

Cited literature (2)

• partial Heroes in oriented complete multipartite graphs (2022)
  Pierre Aboulker et al. · Journal of Graph Theory · arXiv:2202.13306 · doi:10.1002/jgt.23061

  Provides a nearly complete characterization of heroes in oriented complete multipartite graphs, showing heroes in quasi-transitive oriented graphs coincide with those in tournaments, while disproving an analogous equivalence for general oriented multipartite graphs.

• counterexample (Claw, C3)-free Digraphs with Unbounded Dichromatic Number (2026)
  unverified · arXiv preprint · arXiv:2602.08736

  Disproves the conjecture of Aboulker, Charbit and Naserasr that for any hero H and any oriented star forest S, the class of (S,H)-free oriented graphs has bounded dichromatic number, by constructing (Claw, C3)-free orientations of rook graphs with unbounded dichromatic number.

Reviewer notes. Problem 1.2 is a broad open question rather than a specific falsifiable conjecture; it has generated substantial partial results and at least one disproof of a specific related conjecture (the star-forest + hero conjecture from the same paper). A Steiner 2023 paper in J. Graph Theory on coloring digraphs with forbidden induced subgraphs appeared in search results but was not fetched due to the 5-call cap.

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