Sparse obstructions for minor-covering parameters

Dimitris Chatzidimitriou, Dimitrios M. Thilikos, Dimitris Zoros

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)28-50
Number of pages23
JournalDiscrete Applied Mathematics
Volume278
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Sparse obstructions for minor-covering parameters'. Together they form a unique fingerprint.

Cite this