Reading source record 2006-04-14. This record is retained from earlier public citations. View default cited record →
Directed graph questions and partial results from the 2006 workshop
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
Must a simple directed graph with n vertices and minimum out-degree at least r ≥ 1 contain a directed cycle of length at most ⌈n/r⌉?
Passage ID: caccetta-haggkvist:entry:0:v1
Source item: Page 2, Conjecture 2.1
Source record: aim-caccetta@2006-04-14
Shen’s theorem gives the sharp ceiling bound when the vertex count is at least 2r² − 3r + 1.
Passage ID: caccetta-haggkvist:entry:large-order:v1
Source item: §5, Theorem 5.1
Source record: aim-caccetta@2006-04-14
The survey records the conjecture for out-degree parameters two through five, with separate proofs by Caccetta–Häggkvist, Hamidoune and Hoang–Reed.
Passage ID: caccetta-haggkvist:entry:small-degree:v1
Source item: §2.1, known cases; references [8], [22], [25]
Source record: aim-caccetta@2006-04-14
Vertex-transitive directed graphs satisfy the cycle bound, by Hamidoune’s connectivity argument.
Passage ID: caccetta-haggkvist:entry:transitive:v1
Source item: §2.1, vertex-transitive case
Source record: aim-caccetta@2006-04-14
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v9
Source assessment
Proved
Established result in cited source
Shen’s theorem restricts the order relative to the minimum-degree parameter.
Observed Oct 12, 2026
Source assessment
Proved
Established result in cited source
The degree parameter is restricted to two through five; the graph need not be regular.
Observed Oct 12, 2026
Source assessment
Proved
Established result in cited source
Vertex-transitivity requires the automorphism group to act transitively on vertices.
Observed Oct 12, 2026
Source assessment · superseded assessment
Not assessed
Conjecture 2.1; no current-status report
The cited source item and version only; this is not an independent OpenMath assessment.
Source date Apr 14, 2006 · Observed Oct 1, 2026
Question
Caccetta–Häggkvist cycle bound
Further reading
Consult the original question and its hypotheses.
History
Small degree cases are established
Blair D. Sullivan; hosted by American Institute of Mathematics
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
AIM · Caccetta–Häggkvist workshop survey
AIM · Caccetta–Häggkvist workshop survey
Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
Source terms ↗