Kuratowski Chains

Neil Robertson; Paul Seymour; Robin Thomas

doi:10.1006/jctb.1995.1030

Kuratowski Chains

Neil Robertson, Paul Seymour, Robin Thomas

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

17 Scopus citations

Abstract

We prove that if H and H’ are subgraphs of a graph G, and both are isomorphic to subdivisions of K₅ or K_{3, 3}, then the following are equivalent: (i) there is a sequence H = H₁, H₂, ⋯, H_k = H’ of subgraphs of G, each isomorphic to a subdivision of K₅ or K_{3, 3} and each differing only a “small amounty” from its predecessor; (ii) H and H’ are not “separated” in G by a vertex separation of order ≤ 3. This is a lemma for use in a future paper concerning linkless embeddings of graphs in 3-space.

Original language	English (US)
Pages (from-to)	127-154
Number of pages	28
Journal	Journal of Combinatorial Theory, Series B
Volume	64
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1995.1030
State	Published - Jul 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1995.1030

Cite this

@article{298f10ddfe1c427280552b0e496fa018,

title = "Kuratowski Chains",

abstract = "We prove that if H and H{\textquoteright} are subgraphs of a graph G, and both are isomorphic to subdivisions of K5 or K3, 3, then the following are equivalent: (i) there is a sequence H = H1, H2, ⋯, Hk = H{\textquoteright} of subgraphs of G, each isomorphic to a subdivision of K5 or K3, 3 and each differing only a “small amounty” from its predecessor; (ii) H and H{\textquoteright} are not “separated” in G by a vertex separation of order ≤ 3. This is a lemma for use in a future paper concerning linkless embeddings of graphs in 3-space.",

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

year = "1995",

month = jul,

doi = "10.1006/jctb.1995.1030",

language = "English (US)",

volume = "64",

pages = "127--154",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Kuratowski Chains

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

PY - 1995/7

Y1 - 1995/7

N2 - We prove that if H and H’ are subgraphs of a graph G, and both are isomorphic to subdivisions of K5 or K3, 3, then the following are equivalent: (i) there is a sequence H = H1, H2, ⋯, Hk = H’ of subgraphs of G, each isomorphic to a subdivision of K5 or K3, 3 and each differing only a “small amounty” from its predecessor; (ii) H and H’ are not “separated” in G by a vertex separation of order ≤ 3. This is a lemma for use in a future paper concerning linkless embeddings of graphs in 3-space.

AB - We prove that if H and H’ are subgraphs of a graph G, and both are isomorphic to subdivisions of K5 or K3, 3, then the following are equivalent: (i) there is a sequence H = H1, H2, ⋯, Hk = H’ of subgraphs of G, each isomorphic to a subdivision of K5 or K3, 3 and each differing only a “small amounty” from its predecessor; (ii) H and H’ are not “separated” in G by a vertex separation of order ≤ 3. This is a lemma for use in a future paper concerning linkless embeddings of graphs in 3-space.

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

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

U2 - 10.1006/jctb.1995.1030

DO - 10.1006/jctb.1995.1030

M3 - Article

AN - SCOPUS:0039581340

SN - 0095-8956

VL - 64

SP - 127

EP - 154

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Kuratowski Chains

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this