The excluded minors for three classes of 2-polymatroids having special types of natural matroids

Abstract

If $\mathcal{C}$ is a minor-closed class of matroids, the class ${\mathcal{C}}^{\prime }$ of integer polymatroids whose natural matroids are in $\mathcal{C}$ is also minor closed, as is the class ${\mathcal{C}}_k^{\prime }$ of $k$-polymatroids in ${\mathcal{C}}^{\prime }$. We find the excluded minors for ${\mathcal{C}}_2^{\prime }$ when $\mathcal{C}$ is (i) the class of binary matroids, (ii) the class of matroids with no $M(K_4)$-minor, and, combining those, (iii) the class of matroids whose connected components are cycle matroids of series-parallel networks. In each case the class $\mathcal{C}$ has finitely many excluded minors, but that is true of ${\mathcal{C}}_2^{\prime }$ only in case (ii). We also introduce the $k$-natural matroid, a variant of the natural matroid for a $k$-polymatroid, and use it to prove that these classes of 2-polymatroids are closed under 2-duality.

22 pages, 5 figures

References in corpus (1)

• Decomposable polymatroids and connections with graph coloring