Matroids Induced by Packing Subgraphs
Marek Janata · SIAM Journal on Discrete Mathematics · 2004
This paper is concerned with the classification of families of graphs $\mathcal T$ with the following property: For any graph G, the subsets of vertices of G that can be saturated by packing copies of graphs from $\mathcal T$ form a collection of independent sets of a matroid. From this point of view, we present a characterization of so-called EHP-families of graphs (i.e., families consisting of K 2 , hypomatchable graphs, and propellers). The main result is the following: For a matroid-inducing EHP-family $\mathcal T$, we characterize connected graphs H such that the family $\mathcal T\cup\{H\}$ is also matroid-inducing.