Skip to Main content Skip to Navigation
Journal articles

Multigraphs without large bonds are wqo by contraction

Marcin Jakub Kamiński 1 Jean-Florent Raymond 1, 2 Théophile Trunck 1, 3 
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We show that the class of multigraphs with at most p connected components and bonds of size at most k is well-quasi-ordered by edge contraction for all positive integers p, k. (A bond is a minimal non-empty edge cut.) We also characterize canonical antichains for this relation and show that they are fundamental.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Jean-Florent Raymond Connect in order to contact the contributor
Submitted on : Tuesday, June 12, 2018 - 11:19:05 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Thursday, September 13, 2018 - 7:39:09 PM


Files produced by the author(s)



Marcin Jakub Kamiński, Jean-Florent Raymond, Théophile Trunck. Multigraphs without large bonds are wqo by contraction. Journal of Graph Theory, Wiley, 2018, 88 (4), pp.558-565. ⟨10.1002/jgt.22229⟩. ⟨lirmm-01140407v2⟩



Record views


Files downloads