Excluded minors in cubic graphs

Neil Robertson; Paul Seymour; Robin Thomas

doi:10.1016/j.jctb.2019.02.002

Excluded minors in cubic graphs

Neil Robertson, Paul Seymour, Robin Thomas

Mathematics

Princeton University

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

2 Scopus citations

Abstract

Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|≥7 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either • G∖v is planar for some vertex v; or • G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.

Original language	American English
Pages (from-to)	219-285
Number of pages	67
Journal	Journal of Combinatorial Theory. Series B
Volume	138
DOIs	https://doi.org/10.1016/j.jctb.2019.02.002
State	Published - Sep 2019

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Apex graph
Cubic
Graph minors
Petersen graph

Access to Document

10.1016/j.jctb.2019.02.002

Cite this

@article{787f434ffa8f4732a92211c6e18d995f,

title = "Excluded minors in cubic graphs",

abstract = "Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|≥7 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either • G∖v is planar for some vertex v; or • G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.",

keywords = "Apex graph, Cubic, Graph minors, Petersen graph",

author = "Neil Robertson and Paul Seymour and Robin Thomas",

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

year = "2019",

month = sep,

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

language = "American English",

volume = "138",

pages = "219--285",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Excluded minors in cubic graphs

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

PY - 2019/9

Y1 - 2019/9

N2 - Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|≥7 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either • G∖v is planar for some vertex v; or • G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.

AB - Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|≥7 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either • G∖v is planar for some vertex v; or • G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.

KW - Apex graph

KW - Cubic

KW - Graph minors

KW - Petersen graph

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

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

U2 - 10.1016/j.jctb.2019.02.002

DO - 10.1016/j.jctb.2019.02.002

M3 - Article

SN - 0095-8956

VL - 138

SP - 219

EP - 285

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Excluded minors in cubic graphs

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this