Bollobás–Scott linear long-cycle conjecture for Eulerian digraphs

A digraph is Eulerian when it is strongly connected and every vertex has equal in-degree and out-degree. Its average out-degree is the average of the out-degrees of its vertices; denote this quantity by dd. Bollobás–Scott's linear long-cycle conjecture. Every Eulerian digraph with average out-degree dd has a directed cycle of length at least

cdcd

for some universal constant c>0c>0. This is a weaker unweighted version of the weighted Bollobás–Scott conjecture and was proposed as an intermediate step toward resolving it; the source does not state a resolution.

Sources & referencesView supporting material

Primary source

Jiangdong Ai, Gregory Gutin, Fankang He and Anders Yeo, “Note on Long Directed Cycles in Eulerian Digraphs”, arXiv:2510.26426 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.