A separator theorem for nonplanar graphs

Noga Alon, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticle

128 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 languageEnglish (US)
Pages (from-to)801-808
Number of pages8
JournalJournal of the American Mathematical Society
Volume3
Issue number4
DOIs
StatePublished - Oct 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A separator theorem for nonplanar graphs'. Together they form a unique fingerprint.

  • Cite this