Key points are not available for this paper at this time.
Let G G be an n n -vertex graph with no minor isomorphic to an h h -vertex complete graph. We prove that the vertices of G G can be partitioned into three sets A, B, C A, \;B, \;C such that no edge joins a vertex in A A with a vertex in B B, neither A A nor B B contains more than 2 n / 3 2n/3 vertices, and C C contains no more than h 3 / 2 n 1 / 2 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) (A, \;B, \;C) in time O (h 1 <mml: mrow class
Alon et al. (Mon,) studied this question.