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

DOI10.1002/JGT.22408zbMATH Open1414.05273arXiv1707.03563OpenAlexW2963122328WikidataQ129078591 ScholiaQ129078591MaRDI QIDQ4632018FDOQ4632018

Michał Pilipczuk, Florian Barbero, Christophe Paul

Publication date: 25 April 2019

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

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.

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

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

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)

Cited In (4)

• Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Tournaments and Semicomplete Digraphs
• Title not available (Why is that?)

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)