Obstructions to branch-decomposition of matroids

J.F. Geelen, B. Gerards, N. Robertson, G. Whittle

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
1 Downloads (Pure)

Abstract

A (d,¿)-net in a matroid M is a pair where N is a minor of M, is a set of series classes in N, , and the pairwise connectivity, in M, between any two members of is at least ¿. We prove that, for any finite field , nets provide a qualitative characterization for branch-width in the class of -representable matroids. That is, for an -representable matroid M, we prove that: (1) if M contains a (d,¿)-net where d and ¿ are both very large, then M has large branch-width, and, conversely, (2) if the branch-width of M is very large, then M or M* contains a (d,¿)-net where d and ¿ are both large.
Original languageEnglish
Pages (from-to)560-570
JournalJournal of Combinatorial Theory, Series B
Volume96
Issue number4
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Obstructions to branch-decomposition of matroids'. Together they form a unique fingerprint.

Cite this