2025/09/30 by Cavallaro, Dario, Kawarabayashi, Ken-ichi, Kreutzer, Stephan · 1 citation
#05C10 #05C20 #05C45 #05C60 #05C83 #06A06 #06F30 #57N35 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2
paper · doi:10.48550/arxiv.2509.26260
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.