MATROIDS INDUCED BY PACKING SUBGRAPHS

摘要

This paper is concerned with the classification of families of graphs 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 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 T, we characterize connected graphs H such that the family T ∪ {H} is also matroid-inducing.