Excluding sums of Kuratowski graphs

Neil Robertson; Paul Seymour

doi:10.1016/j.jctb.2026.01.001

Excluding sums of Kuratowski graphs

Neil Robertson
, Paul Seymour

Mathematics

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

2 Scopus citations

Abstract

We prove that a graph does not contain as a minor a graph formed by 0-, 1-, 2- or 3-summing k copies of K₅ or K_3,3, if and only if it has bounded genus.

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

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Bounded genus
Graph minors

Access to Document

10.1016/j.jctb.2026.01.001

Cite this

@article{b304ff68ef284afab0231a016e6d2d34,

title = "Excluding sums of Kuratowski graphs",

abstract = "We prove that a graph does not contain as a minor a graph formed by 0-, 1-, 2- or 3-summing k copies of K5 or K3,3, if and only if it has bounded genus.",

keywords = "Bounded genus, Graph 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.001",

language = "English (US)",

volume = "178",

pages = "323--353",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Excluding sums of Kuratowski graphs

AU - Robertson, Neil

AU - Seymour, Paul

PY - 2026/5

Y1 - 2026/5

N2 - We prove that a graph does not contain as a minor a graph formed by 0-, 1-, 2- or 3-summing k copies of K5 or K3,3, if and only if it has bounded genus.

AB - We prove that a graph does not contain as a minor a graph formed by 0-, 1-, 2- or 3-summing k copies of K5 or K3,3, if and only if it has bounded genus.

KW - Bounded genus

KW - Graph minors

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

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

U2 - 10.1016/j.jctb.2026.01.001

DO - 10.1016/j.jctb.2026.01.001

M3 - Article

AN - SCOPUS:105028023359

SN - 0095-8956

VL - 178

SP - 323

EP - 353

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Excluding sums of Kuratowski graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this