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)|
|Number of pages||8|
|Journal||Journal of the American Mathematical Society|
|State||Published - Oct 1990|
All Science Journal Classification (ASJC) codes
- Applied Mathematics