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 R1R1 and R2R2 such that the convex hulls of R1R1 and R2R2 with respect to the P3P3-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 P3P3-convexity of G and complement earlier results in this area.

► We characterize P3P3-Radon-dependent sets in split graphs.
► We describe a linear time recognition algorithm.
► Our results are related to the P3P3-Radon number.