Families of matroids induced by classes of graphs
It is easily proved that, if <em>P</em> is a class of graphs that is closed under induced subgraphs, then the family of matroids whose basis graphs belong to <em>P</em> is closed under minors. We give simple necessary and sufficient conditions for a minor-closed class of matr...
| Κύριος συγγραφέας: | |
|---|---|
| Μορφή: | Journal article |
| Γλώσσα: | English |
| Έκδοση: |
Elsevier
2005
|
| Θέματα: |
| Περίληψη: | It is easily proved that, if <em>P</em> is a class of graphs that is closed under induced subgraphs, then the family of matroids whose basis graphs belong to <em>P</em> 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. |
|---|