Strong immersion is a well-quasi-ordering for semi-complete digraphs

2017/07/12 by Barbero, Florian, Paul, Christophe, Pilipczuk, Michal
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1707.03563

Abstract

We prove that the strong immersion order is a well-quasi-ordering on the class of semi-complete digraphs, thereby strengthening a result of Chudnovsky and Seymour that this holds for the class of tournaments.

Related

• A note on forbidding clique immersions
• Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion
• Immersions of directed graphs in tournaments
• Immersion of transitive tournaments in digraphs with large minimum outdegree
• Effective Computation of Immersion Obstructions for Unions of Graph Classes