On the Carathéodory Number for the Convexity of Paths of Order Three

Let G be a finite, simple, and undirected graph and let S be a set of vertices of G. If no vertex of G that does not belong to S has two neighbours in S, then S is P3-convex. The P3-convex hull HG(S) of S is the smallest P3-convex set containing S. The P3-Carathéodory number of G is the smallest integer c such that for every set S and every vertex u in HG(S), there is a set F⊆S with |F|⩽c and u∈HG(F).We study structural and algorithmic aspects of the P3-Carathéodory number. We characterize the P3-Carathéodory number of trees and block graphs, establish upper bounds on the P3-Carathéodory number of general graphs and of claw-free graphs and prove that it is NP-complete to decide for a given bipartite graph G and a given integer k, whether the P3-Carathéodory number of G is at least k.