The Carathodory number of the P3 P 3 convexity of chordal graphs
If S S is a set of vertices of a graph G G , then the convex hull of S S in the P3 P 3 convexity of G G is the smallest set T T of vertices of G G that contains S S and that has the property that no vertex in V(G)?T V ( G ) ? T has at least two neighbors in T T . The Carathodory number of the P3 P 3 convexity of G G is the smallest integer c c such that for every set S S of vertices of G G and every vertex u u in the convex hull of S S , there is a subset F F of S S with at most c c elements such that u u lies in the convex hull of F F . We describe a polynomial time algorithm to determine the Carathodory number of the P3 P 3 convexity of a given chordal graph.
carathodory number p3 p 3 convexity p3 p 3 p3 p 3 p 3