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

Ignasi Sau; Giannos Stamoulis; Dimitrios M. Thilikos

doi:10.1016/j.jctb.2023.02.012

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

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 order at most 2^{2^{2^{2^poly(k)}}}, where poly is a polynomial function whose degree depends on the order of the minor-obstructions of G. This bound drops to 2^{2^poly(k)} when G excludes some apex graph as a minor.

Original language	English (US)
Pages (from-to)	180-227
Number of pages	48
Journal	Journal of Combinatorial Theory. Series B
Volume	161
DOIs	https://doi.org/10.1016/j.jctb.2023.02.012
State	Published - Jul 2023

Keywords

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

Access to Document

10.1016/j.jctb.2023.02.012

Cite this

@article{b64ec59388bd4daeb90a9294a7b05740,

title = "k-apices of minor-closed graph classes. I. Bounding the obstructions",

abstract = "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.",

keywords = "Flat Wall Theorem, Graph minors, Irrelevant vertex technique, Obstructions, Treewidth",

author = "Ignasi Sau and Giannos Stamoulis and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Inc.",

year = "2023",

month = jul,

doi = "10.1016/j.jctb.2023.02.012",

language = "English (US)",

volume = "161",

pages = "180--227",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

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

AU - Sau, Ignasi

AU - Stamoulis, Giannos

AU - Thilikos, Dimitrios M.

PY - 2023/7

Y1 - 2023/7

N2 - 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.

AB - 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.

KW - Flat Wall Theorem

KW - Graph minors

KW - Irrelevant vertex technique

KW - Obstructions

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85149891138&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85149891138&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.02.012

DO - 10.1016/j.jctb.2023.02.012

M3 - Article

AN - SCOPUS:85149891138

SN - 0095-8956

VL - 161

SP - 180

EP - 227

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this