Characterization and recognition of Radon-independent sets in split graphs
Let R be a set of vertices of a split graph G. We characterize when R allows a partition into two disjoint set R-1 and R-2 such that the convex hulls of R-1 and R-2 with respect to the P-3-convexity of G intersect. Furthermore, we describe a linear time algorithm that decides the existence of such a partition. Our results are related to the so-called Radon number of the P-3-convexity of G and complement earlier results in this area. (c) 2012 Elsevier BM. All rights reserved.
split graph radon number combinatorial problems graph algorithms radon partition graph convexity