Convex p-partitions of bipartite graphs

Abstract

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>1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.