Johnson's bounded-degree Eulerian digraph immersion conjecture

Less than 1 year old · traced to

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 d≥1d\geq 1, consider the class of Eulerian digraphs of maximum degree 2d2d.

Johnson's conjecture. For every d≥1d\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.

References

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.