Martin Dario Safe (Laboratoire MIS (Université de Picardie Jules Verne)

A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p , all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.