Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
This advances structural graph theory by establishing well-quasi-ordering for a broad class of Eulerian digraphs under strong immersion, with implications for algorithmic and combinatorial properties.
The paper proves that Eulerian digraphs of bounded carving width are well-quasi-ordered by strong immersion, and provides a dichotomy result showing that unbounded degree classes are not well-quasi-ordered by strong immersion but may be by weak immersion.
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 seemingly suited to prove well-quasi-ordering for classes of Eulerian directed graphs by (strong) immersion and present a first meta theorem in that direction. We complement our results by observing that the class of Eulerian directed graphs of unbounded degree is \emph{not} well-quasi-ordered by \emph{strong} immersion, even if we assume the treewidth of the class to be at most two. We conclude with a dichotomy result, proving for a very restricted class of Eulerian directed graphs of unbounded degree that it is not well-quasi-ordered by strong immersion, but it is well-quasi-ordered by weak immersion.