## Abstract

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^{cH } 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.

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