Let G be any n-vertex planar graph. It is proved 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 22** one-half n** one-half vertices. An algorithm is exhibited which finds such a partition A, B, C in O(n) time.
All Science Journal Classification (ASJC) codes
- Applied Mathematics