{"id":"arxiv/2605.07468","url":"https://arxiv.org/abs/2605.07468","tags":["cs.DM","math.CO"],"score":0,"title":"Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width","domain":"cs.DM","source":"arxiv","authors":["Dario Cavallaro","Ken-ichi Kawarabayashi","Stephan Kreutzer"],"reviews":0,"subject":"cs.DM","summary":"We prove that every class of Eulerian directed graphs of bounded carving width (equivalently of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we prove a stronger result, namely that every class of Eulerian directed graphs of bounded carving width, where every vertex is additionally labeled from a well-quasi-order, fixes a linear order on its incident edges, and may impose further restrictions on how the immersion is allowed to route paths through it, is well-quasi-ordered by an adequate notion of strong immersion. To this extent, we develop a framework…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-08","reactions":{}}