Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915525281447936 |
|---|---|
| author | Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan |
| author_facet | Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan |
| contents | We prove that for every surface $Σ$, the class of Eulerian directed graphs that are Eulerian embeddable into $Σ$ (in particular they have degree at most $4$) is well-quasi-ordered by strong immersion. This result marks one of the most versatile directed graph classes (besides tournaments) for which we are aware of a positive well-quasi-ordering result regarding a well-studied graph relation.
Our result implies that the class of bipartite circle graphs is well-quasi-ordered under the pivot-minor relation. Furthermore, this also yields two other interesting applications, namely, a polynomial-time algorithm for testing immersion closed properties of Eulerian-embeddable graphs into a fixed surface, and a characterisation of the Erdős-Pósa property for Eulerian digraphs of maximum degree four.
Further, in order to prove the mentioned result, we prove that Eulerian digraphs of carving width bounded by some constant $k$ (which correspond to Eulerian digraphs with bounded treewidth and additionally bounded degree) are well-quasi-ordered by strong immersion. We actually prove a stronger result where we allow for vertices of the Eulerian digraphs to be labeled by elements of some well-quasi-order $Ω$. We complement these results with a proof that the class of Eulerian planar digraphs of treewidth at most $3$ is not well-quasi-ordered by strong immersion, noting that any antichain of bounded treewidth cannot have bounded degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26260 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion Cavallaro, Dario Kawarabayashi, Ken-ichi Kreutzer, Stephan Discrete Mathematics Combinatorics 05C10, 05C20, 05C45, 05C60, 05C83, 06F30, 57N35, 06A06 G.2; F.2 We prove that for every surface $Σ$, the class of Eulerian directed graphs that are Eulerian embeddable into $Σ$ (in particular they have degree at most $4$) is well-quasi-ordered by strong immersion. This result marks one of the most versatile directed graph classes (besides tournaments) for which we are aware of a positive well-quasi-ordering result regarding a well-studied graph relation. Our result implies that the class of bipartite circle graphs is well-quasi-ordered under the pivot-minor relation. Furthermore, this also yields two other interesting applications, namely, a polynomial-time algorithm for testing immersion closed properties of Eulerian-embeddable graphs into a fixed surface, and a characterisation of the Erdős-Pósa property for Eulerian digraphs of maximum degree four. Further, in order to prove the mentioned result, we prove that Eulerian digraphs of carving width bounded by some constant $k$ (which correspond to Eulerian digraphs with bounded treewidth and additionally bounded degree) are well-quasi-ordered by strong immersion. We actually prove a stronger result where we allow for vertices of the Eulerian digraphs to be labeled by elements of some well-quasi-order $Ω$. We complement these results with a proof that the class of Eulerian planar digraphs of treewidth at most $3$ is not well-quasi-ordered by strong immersion, noting that any antichain of bounded treewidth cannot have bounded degree. |
| title | Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion |
| topic | Discrete Mathematics Combinatorics 05C10, 05C20, 05C45, 05C60, 05C83, 06F30, 57N35, 06A06 G.2; F.2 |
| url | https://arxiv.org/abs/2509.26260 |