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 : 2017

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 (214.33 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, 2017, ⟨10.1002/jgt.22229⟩. ⟨lirmm-01140407v1⟩
319 View
340 Download

Altmetric

Share

Gmail Facebook X LinkedIn More