Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

A separator theorem for nonplanar graphs


Authors: Noga Alon, Paul Seymour and Robin Thomas
Journal: J. Amer. Math. Soc. 3 (1990), 801-808
MSC: Primary 05C40; Secondary 05C85, 68Q25, 68R10
DOI: https://doi.org/10.1090/S0894-0347-1990-1065053-0
MathSciNet review: 1065053
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 ${h^{3/2}}{n^{1/2}}$ 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^{1/2}}{n^{1/2}}m)$, where $m = \left | {V(G)} \right | + \left | {E(G)} \right |$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 05C40, 05C85, 68Q25, 68R10

Retrieve articles in all journals with MSC: 05C40, 05C85, 68Q25, 68R10


Additional Information

Article copyright: © Copyright 1990 American Mathematical Society