TY - JOUR
T1 - Obstructions to branch-decomposition of matroids
AU - Geelen, J.F.
AU - Gerards, B.
AU - Robertson, N.
AU - Whittle, G.
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
U2 - 10.1016/j.jctb.2005.11.001
DO - 10.1016/j.jctb.2005.11.001
M3 - Article
SN - 0095-8956
VL - 96
SP - 560
EP - 570
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
IS - 4
ER -