Sparse obstructions for minor-covering parameters.

Given a finite set of graphs H and a non-negative integer k , we define A k (H) as the set containing every graph G that has k vertices whose removal provides a graph without any of the graphs in H as a minor. It is known that if H contains at least one planar graph then each obstruction in A k (H) has at most k c H vertices, for some c H depending only on the choice of H. In this paper, we investigate the size of the graphs in A k (H) that belong to certain classes of sparse graphs. In particular, we prove that for every graph F , if H contains at least one planar graph and only connected graphs, all graphs in A k (H) that are F -topological minor-free have at most c F , H ⋅ k vertices, where c F , H depends exclusively on the choice of H and F. Our result is a consequence of two more general conditions on graph parameters, namely the Finite Integer Index Property and Protrusion Decomposability, that can serve as a general framework for proving linear bounds for obstructions. [ABSTRACT FROM AUTHOR]