Obstructions for bounded branch-depth in matroids
Authors:
- J. Pascal GollinJGJ. Pascal Gollin
- Kevin HendreyKHKevin Hendrey
- Dillon MayhewDMDillon Mayhew
- Sang-Il OumSOSang-Il Oum
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Branch-depth: Generalizing tree-depth of graphsEuropean Journal of Combinatorics, 2020
- Describing quasi-graphic matroidsEuropean Journal of Combinatorics, 2020
- Quasi‐graphic matroids*Journal of Graph Theory, 2017
- First order convergence of matroidsEuropean Journal of Combinatorics, 2017
- Some open problems on excluding a uniform matroidAdvances in Applied Mathematics, 2008
- The structure of the 3-separations of 3-connected matroidsJournal of Combinatorial Theory, Series B, 2004
- The Excluded Minors for GF(4)-Representable MatroidsJournal of Combinatorial Theory, Series B, 2000
- Graph minors. X. Obstructions to tree-decompositionJournal of Combinatorial Theory, Series B, 1991
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986
- The dependence graph for bases in matroidsDiscrete Mathematics, 1977