On the Carathéodory Number for the Convexity of Paths of Order Three
Rommel Barbosa, Erika M. M. Coelho, Mitre Costa Dourado, Dieter Rautenbach, Jayme Luiz SZWARCFITER · SIAM Journal on Discrete Mathematics · 2012
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 neighbors in $S$, then $S$ is $P_3$-convex. The $P_3$-convex hull $H_G(S)$ of $S$ is the smallest $P_3$-convex set containing $S$. The $P_3$-Carathéodory number of $G$ is the smallest integer $c$ such that for every set $S$ and every vertex $u$ in $H_G(S)$, there is a set $F\subseteq S$ with $|F|\leq c$ and $u\in H_G(F)$. We study structural and algorithmic aspects of the $P_3$-Carathéodory number. We characterize the $P_3$-Carathéodory number of trees and block graphs, establish upper bounds on the $P_3$-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 $P_3$-Carathéodory number of $G$ is at least $k$.