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

State | Published - Oct 1990 |

Externally published | Yes |

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

Alon, N., Seymour, P., & Thomas, R. (1990). A separator theorem for nonplanar graphs.

*Journal of the American Mathematical Society*,*3*(4), 801-808. https://doi.org/10.1090/S0894-0347-1990-1065053-0