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

Florian Barbero 1 Christophe Paul 1 Michał Pilipczuk 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We prove that the strong immersion order is a well‐quasi‐ordering on the class of semicomplete digraphs, thereby strengthening a result of Chudnovsky and Seymour (2011, J. Comb. Theory, Series B, 101, 47–53) that this holds for the class of tournaments.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01918986
Contributor : Christophe Paul <>
Submitted on : Monday, November 12, 2018 - 10:01:58 AM
Last modification on : Tuesday, February 19, 2019 - 12:06:09 PM

Links full text

Identifiers

Collections

Citation

Florian Barbero, Christophe Paul, Michał Pilipczuk. Strong immersion is a well-quasi-ordering for semicomplete digraphs. Journal of Graph Theory, Wiley, 2019, 90, pp.484-496. ⟨10.1002/jgt.22408⟩. ⟨lirmm-01918986⟩

Share

Metrics

Record views

51