Johnson's bounded-degree Eulerian digraph immersion conjecture

Let an Eulerian digraph be a directed graph in which every vertex has equal in-degree and out-degree, and let the strong immersion relation be the relation described in the paper. For d1d\geq 1, consider the class of Eulerian digraphs of maximum degree 2d2d.

Johnson's conjecture. For every d1d\geq 1, the class of Eulerian digraphs of maximum degree 2d2d is well-quasi-ordered by strong immersion.

This conjecture would establish well-quasi-ordering for every bounded-degree class of Eulerian digraphs under strong immersion, complementing the paper's antichain showing that unbounded degree prevents such a result. It was previously conjectured by Johnson; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Dario Cavallaro, Ken-ichi Kawarabayashi and Stephan Kreutzer, “Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width”, arXiv:2605.07468 (2026).

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.