posted on 2021-12-01, 19:45authored byJ Pascal Gollin, Kevin Hendrey, Dillon Mayhew, Sang-il Oum
DeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a
natural analogue of tree-depth of graphs. They conjectured that a matroid of
sufficiently large branch-depth contains the uniform matroid $U_{n,2n}$ or the
cycle matroid of a large fan graph as a minor. We prove that matroids with
sufficiently large branch-depth either contain the cycle matroid of a large fan
graph as a minor or have large branch-width. As a corollary, we prove their
conjecture for matroids representable over a fixed finite field and
quasi-graphic matroids, where the uniform matroid is not an option.
History
Preferred citation
Gollin, J. P., Hendrey, K., Mayhew, D. & Oum, S. -I. (2020). Obstructions for bounded branch-depth in matroids. Advances in Combinatorics, 2021:4, 25pp. http://arxiv.org/abs/2003.13975v2