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 :
Pré-publication, Document de travail
2014
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01140407
Contributeur : Jean-Florent Raymond <>
Soumis le : mercredi 8 avril 2015 - 15:08:27
Dernière modification le : jeudi 8 février 2018 - 11:09:28
Document(s) archivé(s) le : jeudi 9 juillet 2015 - 10:47:20

Fichiers

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

Identifiants

  • HAL Id : lirmm-01140407, version 1
  • ARXIV : 1409.2733

Citation

Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck. Multigraphs without large bonds are wqo by contraction. 2014. 〈lirmm-01140407〉

Partager

Métriques

Consultations de la notice

191

Téléchargements de fichiers

170