Multigraphs without large bonds are wqo by contraction

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.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2017, 〈10.1002/jgt.22229〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01140407
Contributeur : Jean-Florent Raymond <>
Soumis le : mardi 12 juin 2018 - 23:19:05
Dernière modification le : jeudi 14 juin 2018 - 01:19:55
Document(s) archivé(s) le : jeudi 13 septembre 2018 - 19:39:09

Fichier

mg-contr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck, Marcin Kami´nskikami´nski. Multigraphs without large bonds are wqo by contraction. Journal of Graph Theory, Wiley, 2017, 〈10.1002/jgt.22229〉. 〈lirmm-01140407v2〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

75