Abstract
Given a finite set of graphs H and a non-negative integer k, we define Ak(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 Ak(H) has at most kcH vertices, for some cH depending only on the choice of H. In this paper, we investigate the size of the graphs in Ak(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 Ak(H) that are F-topological minor-free have at most cF,H⋅k vertices, where cF,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.
Original language | English (US) |
---|---|
Pages (from-to) | 28-50 |
Number of pages | 23 |
Journal | Discrete Applied Mathematics |
Volume | 278 |
DOIs | |
State | Published - May 15 2020 |
Keywords
- Apex-extensions
- Finite integer index
- Graph minors
- Obstruction sets
- Protrusion decompositions
- Tree decompositions
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics