Johnson's bounded-degree Eulerian digraph immersion conjecture
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 , consider the class of Eulerian digraphs of maximum degree .
Johnson's conjecture. For every , the class of Eulerian digraphs of maximum degree 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.