An upper bound on the -Radon number

The generalization of classical results about convex sets in R n to abstract convexity spaces, defined by sets of paths in graphs, leads to many challenging structural and algorithmic problems. Here we study the Radon number for the P 3 -convexity on graphs. R of vertices of a graph G is P 3 -convex if no vertex in V ( G ) ∖ R has two neighbours in R . The P 3 -convex hull of a set of vertices is the smallest P 3 -convex set containing it. The P 3 -Radon number r ( G ) of a graph G is the smallest integer r such that every set R of r vertices of G has a partition R = R 1 ∪ R 2 such that the P 3 -convex hulls of R 1 and R 2 intersect. We prove that r ( G ) ≤ 2 3 ( n ( G ) + 1 ) + 1 for every connected graph G and characterize all extremal graphs.