The conjecture that all orientations of odd cycles are avoidable

From papers

A digraph FF is avoidable if there exists a function dF:NNd_F:\mathbb{N}\rightarrow\mathbb{N} such that every digraph of minimum out-degree at least dF(k)d_F(k) contains an FF-free subdigraph of minimum out-degree at least kk. An orientation of an odd cycle is a digraph obtained by assigning a direction to every edge of a cycle of odd length.

Odd-cycle avoidability conjecture. All orientations of odd cycles are avoidable.

The paper proves avoidability for all orientations of C3C_3 and C5C_5, while showing that the most direct directed extension of Thomassen's conjecture is false. The conjecture remains open for odd cycles beyond the cases established in the paper.

Progress summary

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

Sources & referencesView supporting material

Primary source

Micha Christoph, Barnabás Janzer, Kalina Petrova and Raphael Steiner, “Extending Thomassen's conjecture to directed graphs”, arXiv:2510.11311 (2025).

Solutions 0

No solutions have been posted yet.