Weak immersion conjecture for Eulerian digraphs
Weak immersion conjecture for Eulerian digraphs
Let an Eulerian digraph be a directed graph in which every vertex has equal in-degree and out-degree, and let the weak immersion relation be the immersion relation in which branch vertices may be used internally by routed paths. Consider the class of all Eulerian digraphs.
Weak immersion conjecture. The class of Eulerian digraphs is well-quasi-ordered by weak immersion.
The source presents this as a fundamental contrast with strong immersion: its unbounded-degree antichain relies on forcing high-degree vertices to serve as branch vertices, whereas weak immersion permits them to route other paths. The conjecture remains open in the supplied text.
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.