A separator theorem for nonplanar graphs

Noga Alon; Paul Seymour; Robin Thomas

doi:10.1090/S0894-0347-1990-1065053-0

A separator theorem for nonplanar graphs

Noga Alon, Paul Seymour, Robin Thomas

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

153 Scopus citations

Abstract

Let G be an n-vertex graph with no minor isomorphic to an h-vertex complete graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than (Eqution presented) vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition (A, B, C) in time O(h^½ n^½m) where m = V(G) + E(G).

Original language	English (US)
Pages (from-to)	801-808
Number of pages	8
Journal	Journal of the American Mathematical Society
Volume	3
Issue number	4
DOIs	https://doi.org/10.1090/S0894-0347-1990-1065053-0
State	Published - Oct 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics
Applied Mathematics

Access to Document

10.1090/S0894-0347-1990-1065053-0

Cite this

@article{19a51e3fb833458599c7e1712b6b9d35,

title = "A separator theorem for nonplanar graphs",

abstract = "Let G be an n-vertex graph with no minor isomorphic to an h-vertex complete graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than (Eqution presented) vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition (A, B, C) in time O(h½ n½m) where m = V(G) + E(G).",

author = "Noga Alon and Paul Seymour and Robin Thomas",

year = "1990",

month = oct,

doi = "10.1090/S0894-0347-1990-1065053-0",

language = "English (US)",

volume = "3",

pages = "801--808",

journal = "Journal of the American Mathematical Society",

issn = "0894-0347",

publisher = "American Mathematical Society",

number = "4",

}

TY - JOUR

T1 - A separator theorem for nonplanar graphs

AU - Alon, Noga

AU - Seymour, Paul

AU - Thomas, Robin

PY - 1990/10

Y1 - 1990/10

N2 - Let G be an n-vertex graph with no minor isomorphic to an h-vertex complete graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than (Eqution presented) vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition (A, B, C) in time O(h½ n½m) where m = V(G) + E(G).

AB - Let G be an n-vertex graph with no minor isomorphic to an h-vertex complete graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than (Eqution presented) vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition (A, B, C) in time O(h½ n½m) where m = V(G) + E(G).

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

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

U2 - 10.1090/S0894-0347-1990-1065053-0

DO - 10.1090/S0894-0347-1990-1065053-0

M3 - Article

AN - SCOPUS:84968494230

SN - 0894-0347

VL - 3

SP - 801

EP - 808

JO - Journal of the American Mathematical Society

JF - Journal of the American Mathematical Society

IS - 4

ER -

A separator theorem for nonplanar graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this