Open
Open question in cited source ↗
Counting flags in triangle-free digraphs · §1, triangle specialization →
Observed Oct 12, 2026
Conjecture · version 1
The one-third directed triangle question
Statement
Every finite oriented graph on n ≥ 1 vertices with minimum out-degree at least n/3 contains a directed triangle.
Assumptions
- Oriented graphs have no loops, parallel arcs or opposite arcs; this is a specialization of the full conjecture.
Evidence
Source reports
Connections
In this problem · publication v11 · Selected context
Caccetta–Häggkvist cycle bound →
Different statement · related variant · Open
Related statements
The one-third triangle question is a specialization for oriented graphs.
Settling this specialization alone would not settle every n and r.
Details & sources
The full directed cycle bound →
Open · version 2
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⌉?
- Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
Scope: Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
The one-third directed triangle question →
Open · version 1
Every finite oriented graph on n ≥ 1 vertices with minimum out-degree at least n/3 contains a directed triangle.
- Oriented graphs have no loops, parallel arcs or opposite arcs; this is a specialization of the full conjecture.
Scope: Oriented graphs have no loops, parallel arcs or opposite arcs; this is a specialization of the full conjecture.
- Counting flags in triangle-free digraphs →
- Aharoni’s rainbow cycle conjecture holds up to an additive constant →
Relationship not independently reviewed.
Connection in Caccetta–Häggkvist cycle bound →Relationship not independently reviewed. This concerns its use in this problem.
Sources
Aharoni’s rainbow cycle conjecture holds up to an additive constant →
- §1, Conjectures 1.1 and 1.3; reduction following Conjecture 1.3 → · Original passage ↗
Recorded wording
The rainbow conjecture asks for a cycle with distinct edge colors and length at most ⌈n/r⌉ when n color classes in a simple n-vertex graph each have at least r edges. Coloring directed edges by their tails shows this would imply the Caccetta–Häggkvist conjecture.
paraphrase · Follow the original source for authoritative statements and reuse terms.
Patrick Hompe · Tony Huynh · Published · Publication date May 2025
Source-backed selection; publication and proof assessment are separate.
Revision & attribution
Source revision: arxiv-2212.05697v4. Observed Oct 12, 2026.
AI use is not reported in the selected source.
Counting flags in triangle-free digraphs →
- §1, triangle specialization → · Original passage ↗
Recorded wording
The triangle specialization asks for a directed triangle at minimum out-degree at least one third of the vertex count, in an oriented graph.
paraphrase · Follow the original source for authoritative statements and reuse terms.
Jan Hladký · Daniel Král’ · Sergey Norin · Published · Publication date 2017
Source-backed selection; publication and proof assessment are separate.
Revision & attribution
Source revision: arxiv-0908.2791v4. Observed Oct 12, 2026.
AI use is not reported in the selected source.
AIM · Caccetta–Häggkvist workshop survey →
- Page 2, Conjecture 2.1 → · Original passage ↗
Recorded wording
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⌉?
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
Blair D. Sullivan; hosted by American Institute of Mathematics · Revision 2006-04-14-sha256-98251ac3
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Open
Open question in cited source ↗
Observed Oct 12, 2026 · Source passage →
Record details
- Claim ID
- claim-ch-triangle-target
- Statement version
- 1
- SHA-256
- 58060e46dd7420b0cc87ff4a5560480149fb8eca1afac755e320834dde011fa0