k-apices of minor-closed graph classes. I. Bounding the obstructions

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G∖S belongs to G. We denote by Ak(G) the set of all graphs that are k-apices of G. We prove that every graph in the obstruction set of Ak(G), i.e., the minor-minimal set of graphs not belonging to Ak(G), has order at most 2222poly(k), where poly is a polynomial function whose degree depends on the order of the minor-obstructions of G. This bound drops to 22poly(k) when G excludes some apex graph as a minor.

Original languageEnglish (US)
Pages (from-to)180-227
Number of pages48
JournalJournal of Combinatorial Theory. Series B
StatePublished - Jul 2023


  • Flat Wall Theorem
  • Graph minors
  • Irrelevant vertex technique
  • Obstructions
  • Treewidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'k-apices of minor-closed graph classes. I. Bounding the obstructions'. Together they form a unique fingerprint.

Cite this