openmath.dev
Esc

Loading…

↑ ↓ to move↵ to open

Appearance
Appearance

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

Connections

In this problem · publication v4 · 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 1

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.

Relationship not independently reviewed.

Connection in Caccetta–Häggkvist cycle bound →

Relationship not independently reviewed. This concerns its use in this problem.

In this problem · publication v11

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.

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.

Record details
Claim ID
claim-ch-triangle-target
Statement version
1
SHA-256
58060e46dd7420b0cc87ff4a5560480149fb8eca1afac755e320834dde011fa0

Publication records