Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9506023 | Advances in Applied Mathematics | 2005 | 18 Pages |
Abstract
It is easily proved that, if P is a class of graphs that is closed under induced subgraphs, then the family of matroids whose basis graphs belong to P is closed under minors. We give simple necessary and sufficient conditions for a minor-closed class of matroids to be induced in this way, and characterise when such a class of matroids contains arbitrarily large connected matroids. We show that five easily-defined families of matroids can be induced by a class of graphs in this manner: binary matroids; regular matroids; the polygon matroids of planar graphs; those matroids for which every connected component is either graphic or cographic; and those matroids for which every connected component is either binary or can be obtained from a binary matroid by a single circuit-hyperplane relaxation. We give an excluded-minor characterisation of the penultimate class, and show that the last of these classes has infinitely many excluded minors.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Dillon Mayhew,