Multigraphs without large bonds are wqo by contraction
Preprint
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.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Graph minors XXIII. Nash-Williams' immersion conjectureJournal of Combinatorial Theory, Series B, 2010
- On canonical antichainsDiscrete Mathematics, 2009
- Graph Minors. XX. Wagner's conjectureJournal of Combinatorial Theory, Series B, 2004
- Induced subgraphs and well‐quasi‐orderingJournal of Graph Theory, 1990