Multigraphs without large bonds are wqo by contraction

DOI10.1002/JGT.22229zbMATH Open1393.05255arXiv1412.2407OpenAlexW2963829260MaRDI QIDQ4581283FDOQ4581283

Authors: Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck 

Publication date: 16 August 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1412.2407

Recommendations

• Well-quasi-ordering \(H\)-contraction-free graphs
• scientific article; zbMATH DE number 3926975
• Subgraphs and well‐quasi‐ordering
• Induced subgraphs and well‐quasi‐ordering
• Labelled induced subgraphs and well-quasi-ordering

zbMATH Keywords

antichainscontractionswell-quasi-orderingcanonical antichains

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (05C99)

Cited In (1)

• Well-quasi-ordering \(H\)-contraction-free graphs

This page was built for publication: Multigraphs without large bonds are wqo by contraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581283)