Excluding disjoint Kuratowski graphs

Neil Robertson; Paul Seymour

doi:10.1016/j.jctb.2026.01.002

Excluding disjoint Kuratowski graphs

Neil Robertson
, Paul Seymour

Mathematics

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

Abstract

A graph is a k-Kuratowski graph if it has exactly k components, each isomorphic to K₅ or to K_3,3. We prove that if a graph G contains no k-Kuratowski graph as a minor, then there is a set X of boundedly many vertices such that G∖X can be drawn in a (possibly disconnected) surface in which no k-Kuratowski graph can be drawn.

Original language	English (US)
Pages (from-to)	294-322
Number of pages	29
Journal	Journal of Combinatorial Theory. Series B
Volume	178
DOIs	https://doi.org/10.1016/j.jctb.2026.01.002
State	Published - May 2026

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Bounded genus
Excluded minors

Access to Document

10.1016/j.jctb.2026.01.002

Cite this

@article{7bd8643bbe734fe09bb93285a9b955c8,

title = "Excluding disjoint Kuratowski graphs",

abstract = "A graph is a k-Kuratowski graph if it has exactly k components, each isomorphic to K5 or to K3,3. We prove that if a graph G contains no k-Kuratowski graph as a minor, then there is a set X of boundedly many vertices such that G∖X can be drawn in a (possibly disconnected) surface in which no k-Kuratowski graph can be drawn.",

keywords = "Bounded genus, Excluded minors",

author = "Neil Robertson and Paul Seymour",

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

year = "2026",

month = may,

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

language = "English (US)",

volume = "178",

pages = "294--322",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Excluding disjoint Kuratowski graphs

AU - Robertson, Neil

AU - Seymour, Paul

PY - 2026/5

Y1 - 2026/5

N2 - A graph is a k-Kuratowski graph if it has exactly k components, each isomorphic to K5 or to K3,3. We prove that if a graph G contains no k-Kuratowski graph as a minor, then there is a set X of boundedly many vertices such that G∖X can be drawn in a (possibly disconnected) surface in which no k-Kuratowski graph can be drawn.

AB - A graph is a k-Kuratowski graph if it has exactly k components, each isomorphic to K5 or to K3,3. We prove that if a graph G contains no k-Kuratowski graph as a minor, then there is a set X of boundedly many vertices such that G∖X can be drawn in a (possibly disconnected) surface in which no k-Kuratowski graph can be drawn.

KW - Bounded genus

KW - Excluded minors

UR - https://www.scopus.com/pages/publications/105028281059

UR - https://www.scopus.com/pages/publications/105028281059#tab=citedBy

U2 - 10.1016/j.jctb.2026.01.002

DO - 10.1016/j.jctb.2026.01.002

M3 - Article

AN - SCOPUS:105028281059

SN - 0095-8956

VL - 178

SP - 294

EP - 322

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Excluding disjoint Kuratowski graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this