Directed graph questions and partial results from the 2006 workshop
4 cited passages ↓1 problem ↓Record 2006-04-14-sha256-98251ac3 ↓
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⌉?
Replaces an earlier passage. View versioned records →
Passage ID: caccetta-haggkvist:entry:0:v2
Source item: Page 2, Conjecture 2.1
Source record: aim-caccetta@2006-04-14-sha256-98251ac3
Replaces passage: caccetta-haggkvist:entry:0:v1
Shen’s theorem gives the sharp ceiling bound when the vertex count is at least 2r² − 3r + 1.
Replaces an earlier passage. View versioned records →
Passage ID: caccetta-haggkvist:entry:large-order:v2
Source item: §5, Theorem 5.1
Source record: aim-caccetta@2006-04-14-sha256-98251ac3
Replaces passage: caccetta-haggkvist:entry:large-order:v1
The survey records the conjecture for out-degree parameters two through five, with separate proofs by Caccetta–Häggkvist (r = 2), Hamidoune (r = 3) and Hoàng–Reed (r = 4, 5).
Replaces an earlier passage. View versioned records →
Passage ID: caccetta-haggkvist:entry:small-degree:v2
Source item: §2.1, Partial Results; references [5], [17], [19]
Source record: aim-caccetta@2006-04-14-sha256-98251ac3
Replaces passage: caccetta-haggkvist:entry:small-degree:v1
Vertex-transitive directed graphs satisfy the cycle bound, by Hamidoune’s connectivity argument.
Replaces an earlier passage. View versioned records →
Passage ID: caccetta-haggkvist:entry:transitive:v2
Source item: §2.1, vertex-transitive case
Source record: aim-caccetta@2006-04-14-sha256-98251ac3
Replaces passage: caccetta-haggkvist:entry:transitive:v1
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v11
Source assessment
Proved
Established result in cited source
Shen’s theorem restricts the order relative to the minimum-degree parameter.
Observed Oct 21, 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 21, 2026
Source assessment
Proved
Established result in cited source
Vertex-transitivity requires the automorphism group to act transitively on vertices.
Observed Oct 21, 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 ↗