Bipartite Caccetta–Häggkvist short cycle

Conjecture 1.2 · arXiv:1809.08324

arXiv Conjecture high confidence— first stated 2019-07-24

Authors: Paul Seymour, Sophie Spirkl

Status partial high confidence

The source paper (published in Combinatorica 2020) itself proves Conjecture 1.2 for k = 1, 2, 3, 4, 6 and all k ≥ 224,539, establishing substantial partial progress. The full conjecture remains open for the intermediate values 5 and 7 ≤ k ≤ 224,538. No post-2019 follow-up paper extending these results to additional cases was found across multiple targeted searches.

Reviewer notes. The partial results (k=1,2,3,4,6 and k≥224,539) are all from the source paper itself, not from subsequent literature. The conjecture is implied by the Caccetta-Häggkvist conjecture; resolving the latter would settle this one. No follow-up paper found in indexed literature as of May 2026.

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

Conjecture. For every integer $k \geq 1$, if $G$ is a bipartite digraph, with $n > 0$ vertices in each part, and every vertex has out-degree more than $n/(k+1)$, then $G$ has girth at most $2k$.

Context

The central bipartite analogue of the Caccetta-Häggkvist conjecture, motivated by an extremal construction with bipartition into parts of cardinality $(k+1)t$ in which every vertex has out-degree exactly $n/(k+1)$ and no directed cycle of length at most $2k$ exists. The conjecture is implied by the Caccetta-Häggkvist conjecture.

Source paper

Short directed cycles in bipartite digraphs
Paul Seymour, Sophie Spirkl · 2019-07-24
https://arxiv.org/abs/1809.08324 PDF source