Strong immersion is a well-quasi-ordering for semicomplete digraphs

DOI10.1002/JGT.22408MaRDI QIDQ4632018zbMATH OpenOpenAlexWikidataFDO

Authors Florian Barbero, Christophe Paul, Michał Pilipczuk

Publication date 25 April 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03563

zbMATH Keywords

well-quasi-orderingsemicomplete digraphsimmersion order

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph minors (05C83)

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.

Recommendations

• A well-quasi-order for tournaments
• Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
• Well-quasi-ordering hereditarily finite sets
• On well quasi-order of graph classes under homomorphic image orderings
• On well-quasi-ordering-finite graphs by immersion

Cited in

(9)

• Immersion of complete digraphs in Eulerian digraphs
• Immersing complete digraphs
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Tournaments and Semicomplete Digraphs
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Well-quasi-ordering hereditarily finite sets
• Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
• A well-quasi-order for tournaments
• Tournament immersion and cutwidth

This page was built for publication: Strong immersion is a well-quasi-ordering for semicomplete digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632018)