zbMATH — the first resource for mathematics

A separator theorem for nonplanar graphs. (English) Zbl 0747.05051
Let \(G\) be an \(n\)-vertex graph with no minor, a graph which can be obtained from a subgraph of \(G\) by contracting edges, isomorphic to an \(h\)-vertex complete graph. The authors 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 R. J. Lipton and R. E. Tarjan [SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)].
Reviewer: M.Hager (Leonberg)

05C40 Connectivity
05C10 Planar graphs; geometric and topological aspects of graph theory
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] 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. · Zbl 0556.05022 · doi:10.1016/0196-6774(84)90019-1 · doi.org
[2] Richard J. Lipton and Robert Endre Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), no. 2, 177 – 189. · Zbl 0432.05022 · doi:10.1137/0136016 · doi.org
[3] 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. · Zbl 0795.05110 · doi:10.1006/jctb.1993.1027 · doi.org
[4] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.