Problem dossier · Graph Theory
Caccetta–Häggkvist conjecture
Every digraph on n vertices with minimum out-degree r contains a directed cycle of length at most ⌈n/r⌉.
§1
Status
Open. The hardest case is r = n/3 (a directed triangle); best results get triangles at out-degree ≈ 0.3465n (Hladký–Král–Norin refinements of Shearer's bound).
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Build random and structured digraphs near the conjectured threshold and search for short cycles; hunt extremal digraphs with large girth-to-degree ratio in small n.
Tags: digraphs · cycles · girth · out-degree
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Theory and adjacent territory.
- Goemans' unsplittable-flow cost conjecture — Graph Theory
- Graffiti conjecture 284 — Graph Theory
- Erdős–Faber–Lovász conjecture — Graph Theory
- Frankl's union-closed sets conjecture — Graph Theory
- Lonely runner conjecture — Graph Theory
- No-three-in-line problem — Graph Theory