Multigraphs without large bonds are wqo by contraction

DOI10.1002/JGT.22229MaRDI QIDQ4581283zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

antichainscontractionswell-quasi-orderingcanonical antichains

Mathematics Subject Classification ID

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

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.

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

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)