2026-09-05T11:38:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26440 2026-08-27T14:39:31Z ddc:004 open_access

Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan algorithmic graph theory structural graph theory digraphs immersions well-quasi ordering 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 labelled 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 not well-quasi-ordered by 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dario Cavallaro and Ken-ichi Kawarabayashi and Stephan Kreutzer 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.51 urn:nbn:de:0030-drops-264404 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.51 eng https://creativecommons.org/licenses/by/4.0/legalcode