Paper Info
Title
Families of matroids induced by classes of graphs
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.
Year
DOI
Venue
2005
10.1016/j.aam.2004.11.001
Advances in Applied Mathematics
Keywords
Field
DocType
binary matroids,basis graph,penultimate class,polygon matroids,induced subgraphs,minor-closed class,connected component,binary matroid,regular matroids,large connected matroids,planar graph
Matroid,Discrete mathematics,Polygon,Combinatorics,Clique-sum,Graphic matroid,Connected component,Planar graph,Mathematics,Branch-decomposition,Binary number
Journal
Volume
Issue
ISSN
34
3
0196-8858
Citations 
PageRank 
References 
2
0.44
2
Authors
1
Name
Order
Citations
PageRank
Dillon Mayhew110218.63