Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918489336315904 |
|---|---|
| author | Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan |
| author_facet | Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07468 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan Discrete Mathematics Combinatorics 68R10 G.2.1; G.2.2 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. |
| title | Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width |
| topic | Discrete Mathematics Combinatorics 68R10 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2605.07468 |