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

Abstract: Let

m a t h c a l G

be a minor-closed graph class. We say that a graph

G

is a

k

-apex of

m a t h c a l G

if

G

contains a set

S

of at most

k

vertices such that

G s e t m i n u s S

belongs to

m a t h c a l G .

We denote by

m a t h c a l A_{k} (m a t h c a l G)

the set of all graphs that are

k

-apices of

m a t h c a l G .

We prove that every graph in the obstruction set of

m a t h c a l A_{k} (m a t h c a l G),

i.e., the minor-minimal set of graphs not belonging to

m a t h c a l A_{k} (m a t h c a l G),

has size at most

2^{2^{2^{2^{m a t h s f p o l y (k)}}}},

where

m a t h s f p o l y

is a polynomial function whose degree depends on the size of the minor-obstructions of

m a t h c a l G .

This bound drops to

2^{2^{m a t h s f p o l y (k)}}

when

m a t h c a l G

excludes some apex graph as a minor.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions