Multigraphs without large bonds are wqo by contraction - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Graph Theory Year : 2018

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.
Fichier principal
Vignette du fichier
mg-contr.pdf (259.94 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01140407 , version 1 (08-04-2015)
lirmm-01140407 , version 2 (12-06-2018)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More