Caccetta-Häggkvist Conjecture

Status open high confidence

The Caccetta-Häggkvist conjecture remains open in its full generality, including the well-known case $r = n/3$ (existence of a directed triangle). Post-2013 work has produced only partial results: improvements on the digraph triangle bound, proofs for restricted classes (e.g., small independence number, forbidden subgraphs), counterexamples to a stronger conjecture of Thomassé, and progress on Aharoni's rainbow generalization (now resolved up to a constant factor and up to an additive constant).

Cited literature (9)

• partial On the length of directed paths in digraphs (2024)
  Yangyang Cheng, Peter Keevash · arXiv preprint · arXiv:2402.16776

  Disproves Thomassé's strengthening of the Caccetta-Häggkvist conjecture for all girth $g \geq 4$ and proves new lower bounds on directed path lengths in digraphs of given minimum out-degree and girth.

• partial Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (2022)
  Patrick Hompe, Zishen Qu, Sophie Spirkl · arXiv preprint · arXiv:2206.10733

  Establishes improved triangle-existence bounds in Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture, e.g. that $(1.1077, 1/3)$ is triangular and $(1, 0.3988)$ is triangular.

• partial Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (2021)
  Patrick Hompe, Sophie Spirkl · arXiv preprint · arXiv:2105.03373

  Proves Aharoni's rainbow version of the Caccetta-Häggkvist conjecture holds when each color class has size $\Omega(k)$, improving the previous $\Omega(k \log k)$ requirement and bringing the result to within a constant factor of the conjecture.

• partial Aharoni's rainbow cycle conjecture holds up to an additive constant (2022)
  Patrick Hompe, Tony Huynh · arXiv preprint · arXiv:2212.05697

  Shows that Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture holds up to an additive constant: edge-colored graphs with $n$ vertices and $n$ color classes of size at least $r$ contain a rainbow cycle of length at most $n/r + \alpha_r$.

• partial Short rainbow cycles in edge-colored graphs (2023)
  Xiaozheng Chen, Shanshan Guo, Fei Huang · arXiv preprint · arXiv:2311.12302

  Proves that for edge-colored graphs on $n$ vertices with $n$ color classes (each a matching of size 2 or a triangle) of which at least $\alpha n$ have a given form for $\alpha > 1/2$, the graph contains a rainbow cycle of length $O(\log n)$, contributing to Aharoni's rainbow version of the Caccetta-Häggkvist conjecture.

• partial Decomposing and colouring some locally semicomplete digraphs (2022)
  Pierre Aboulker, Guillaume Aubian, Pierre Charbit · arXiv preprint · arXiv:2103.07886

  Proves that every locally in-tournament digraph satisfies the Caccetta-Häggkvist conjecture, deducing it from the structural decomposition theorem (Theorem 2.3).

• partial Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (2023)
  Patrick Hompe, Zishen Qu, Sophie Spirkl · arXiv preprint · arXiv:2206.10733

  Does not prove new bounds for the conjecture directly; instead uses existing approximations for the triangle case as a tool to establish improved triangularity bounds for Aharoni's rainbow generalization, and notes that improvements to those approximations would yield improvements to Theorem 3.

• partial Short rainbow cycles in graphs and matroids (2020)
  Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, Amanda Montejano · arXiv preprint · arXiv:1806.00825

  Proves the $r=2$ case of Aharoni's rainbow strengthening of this conjecture (Theorem 5), which implies the $r=2$ case of Caccetta-Häggkvist. Also introduces Conjecture 4, a weaker rainbow properly-coloured-cycle condition shown to imply the full Caccetta-Häggkvist conjecture.

• partial Short directed cycles in bipartite digraphs (2019)
  Paul Seymour, Sophie Spirkl · arXiv preprint · arXiv:1809.08324

  Shows that the Caccetta-Häggkvist conjecture implies the bipartite analogue Conjecture 1.2; uses CH-approximations to prove 1.2 for $k = 1, 2, 3, 4, 6$, and all $k \geq 224{,}539$.

Reviewer notes. The original Caccetta-Häggkvist conjecture is unresolved, including the central r = n/3 (triangle) case. Most recent activity post-2013 concerns either Aharoni's rainbow generalization or strengthenings/restrictions (small independence number, forbidden subgraphs). The 2024 Cheng-Keevash paper disproves a strictly stronger conjecture of Thomassé but does not affect the original Caccetta-Häggkvist statement. The SIAM page for Devlin/Aharoni-style 'Nonuniform Degrees' rainbow paper returned 403 and was not directly verified, so it is not cited.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).