## A separator theorem for nonplanar graphs

HTML articles powered by AMS MathViewer

- by Noga Alon, Paul Seymour and Robin Thomas
- J. Amer. Math. Soc.
**3**(1990), 801-808 - DOI: https://doi.org/10.1090/S0894-0347-1990-1065053-0
- PDF | Request permission

## 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

- John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan,
*A separator theorem for graphs of bounded genus*, J. Algorithms**5**(1984), no. 3, 391–407. MR**756165**, DOI 10.1016/0196-6774(84)90019-1 - Richard J. Lipton and Robert Endre Tarjan,
*A separator theorem for planar graphs*, SIAM J. Appl. Math.**36**(1979), no. 2, 177–189. MR**524495**, DOI 10.1137/0136016 - P. D. Seymour and Robin Thomas,
*Graph searching and a min-max theorem for tree-width*, J. Combin. Theory Ser. B**58**(1993), no. 1, 22–33. MR**1214888**, DOI 10.1006/jctb.1993.1027
N. Alon, P. D. Seymour, and R. Thomas,

*A separator theorem for graphs with an excluded minor and its applications*(Proc. 22nd STOC, Baltimore, Maryland, 1990), ACM Press, 293-299.

## Bibliographic Information

- © Copyright 1990 American Mathematical Society
- 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