The excluded minors for k-polymatroids with binary k-natural matroids

2023/04/05 by Fiona Young, Young, Fiona
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2304.02743

Abstract

If C is a minor-closed class of matroids, then the class \widetildeC'_k of k-polymatroids whose k-natural matroids are in C is also minor-closed. We investigate the following question: When C is the class of binary matroids, what are the excluded minors for \widetildeC'_k? When k = 1, \widetildeC'₁ is simply the class of binary matroids, which has U_2,4 as its only excluded minor. Joseph E. Bonin and Kevin Long answered the question for k = 2 and found that the set of excluded minors for \widetildeC'₂ is infinite. We determine the sets of excluded minors for \widetildeC'_k when k ≥ 3 and find that they are finite. There are 12 excluded minors for \widetildeC'₃ and when k > 3, there are k+7 excluded minors for \widetildeC'_k.

Related

• The essential bound of a polymatroid and its applications to excluded minor problems
• The excluded minors for lattice path polymatroids
• Classes of binary matroids with small lists of excluded induced minors
• Excluded minors for the class of split matroids
• Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k