Logo image
Sign in
Back
Multigraphs without large bonds are wqo by contraction
Journal article   Open access   Peer reviewed

Multigraphs without large bonds are wqo by contraction

Marcin Jakub Kamiński, Jean-Florent Raymond and Théophile Trunck
Journal of Graph Theory, Vol.88(4), pp.558-565
08/2018
DOI: https://doi.org/10.1002/jgt.22229

Abstract

Structural graph theory Graph decomposition Well-quasi-ordering G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory
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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image