k-apices of minor-closed graph classes. I. Bounding the obstructions
share
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 A_k ( G) the set of all graphs that are k-apices of G. We prove that every graph in the obstruction set of A_k ( G), i.e., the minor-minimal set of graphs not belonging to A_k ( G), has size at most 2^2^2^2^ poly(k), where poly is a polynomial function whose degree depends on the size of the minor-obstructions of G. This bound drops to 2^2^ poly(k) when G excludes some apex graph as a minor.
READ FULL TEXT