Before revision: A bipartite graph G=(A,B,E) is {\cal H}-convex, for some family of graphs {\cal H}, if there exists a graph H\in {\cal H} with V(H)=A such that the set of neighbours in A of each b\in B induces a connected subgraph of H. A variety of well-known NP-complete problems, including Dominating Set ,Feedback Vertex Set ,Induced Matching andList k-Colouring , become polynomial-time solvable for {\mathcal H}-convex graphs when {\mathcal H} is the set of paths.
After revision: A bipartite graph G=(A,B,E) is {\cal H}-convex, for some family of graphs {\cal H}, if there exists a graph H\in {\cal H} with V(H)=A such that the set of neighbours in A of each b\in B induces a connected subgraph of H. Many NP-complete problems, including Dominating Set ,Feedback Vertex Set ,Induced Matching andList k-Colouring , become polynomial-time solvable for {\mathcal H}-convex graphs when {\mathcal H} is the set of paths.