Abstract
A set C of vertices of a graph is P 3 -convex if every vertex outside C has at most one neighbor in C. The convex hull σ(A) of a set A is the smallest P3-convex set that contains A. A set M is convexly independent if for every vertex x ∈ M, x ∉ σ(M - x). We show that the maximal number of vertices that a convexly independent set in a permutation graph can have, can be computed in polynomial time. (Due to space limit, the missing proofs are presented in the full paper. Please see https://drive.google.com/file/d/0B1Ilu0-p1dDsSkpsZFZsR1Y4Uk0/view or http://arxiv.org/abs/1609.02657).