There are only a finite number of excluded minors for the class of bicircular matroids
Matt DeVos, Daryl Funk, Luis Goddyn, Gordon Royle · Advances in Combinatorics · 2023
In 1937, Wagner proved that a graph is planar if and only if it has neither $K_5$ nor $K_{3,3}$ as a minor, where one obtains a minor of a graph by a sequence of deletions or contractions of edges or deletion of vertices. Thus, Wagner proved that $\{K_5, K_{3,3}\}$ is the set of excluded minors for the class of planar graphs. A celebrated result of Robertson and Seymour proves the far-reaching extension of Wagner's Theorem that, for every class of graphs that is closed under taking minors, the set of excluded minors is finite. Whitney introduced [matroids](https://en.wikipedia.org/wiki/Matroid) to abstractly capture the notion of linear dependence. For example, from every matrix, one obtains a matroid whose elements are the matrix's column labels and whose independent sets are the linearly independent sets of columns. In particular, the vertex-edge incidence matrix of a graph, interpreted over the 2-element field, gives rise to a graphic matroid. Like graphs, matroids have substructures called [minors](https://en.wikipedia.org/wiki/Matroid_minor); these are obtained by a sequence of deletions and contractions of elements. Unlike graphs, matroids have numerous minor-closed subclasses that cannot be characterized by a finite set of excluded minors. Indeed, precisely which natural classes of matroids have such a characterization is unknown. It has been announced that, for a fixed field, the set of matroids that arise from matrices over that field has a finite set of excluded minors exactly when the field is finite, although the proof of this result has yet to appear. In 1959, Tutte proved that the class of [graphic matroids](https://en.wikipedia.org/wiki/Graphic_matroid) has five excluded minors. The class of [bicircular matroids](https://en.wikipedia.org/wiki/Bicircular_matroid) is another well-studied and natural class of matroids arising from graphs. Specifically, the bicircular matroid of a graph is the matroid on the edge set of the graph where a set $I$ of edges is independent exactly when there is a corresponding set of $|I|$ distinct vertices such that each edge meets its corresponding vertex. This paper proves that the class of bicircular matroids can be characterized by a finite set of excluded minors.