# Restricting the concept of “hereditary” property to bipartite graphs

We say that a property $\Pi$ is hereditary if whenever $G=(V,E)$ satisfies $\Pi$ then any induced subgraph $G[V']$ (with $V' \subseteq V$) satisfies $\Pi$.

I was wondering whether there is a proper name for the same concept when restricted to bipartite graphs. For example:

Given a bipartite graph G=(V,W,E), where V and W are the two independent sets of vertices, we call a property $\Pi$ "V-hereditary" (resp. "W-hereditary") if whenever $G$ satisfies $\Pi$ then any induced subgraph $G[V' \cup W]$ (resp. $G[V \cup W']$) satisfies $\Pi$ (with $V' \subseteq V$ and $W' \subseteq W'$).

Thank you very much!

EDIT I corrected the question after Oliver observation. The idea is that I allow removal only from one of the two sets.

-

Your restriction is the same as the usual definition. Indeed, clearly a (vertex-)hereditary property is also "bipartite hereditary". Now suppose $\Pi$ is "bipartite hereditary". Suppose $\Pi$ holds for a bipartite graph $G$ on $V = V_1 \cup V_2$ ($V_1,V_2$ are the two parts). Suppose we're given some $V' \subset V$. Since $\Pi$ is bipartite hereditary, then $\Pi$ holds for $G[V_1 \cup (V_2 \cap V')]$. Using the property again, $\Pi$ also holds for $G[(V_1 \cap V') \cup (V_2 \cap V')] = G[V']$.

As far as I know, a hereditary property is usually defined to be closed under taking arbitrary subgraphs, not only induced.

-

I think there is unlikely to be a name for this concept. The graph $G[V']$ has no edges, and hence is not a terribly interesting object of study.

-
Yes, you are right, the way I wrote it would return an edge-less set. I should write $G[V' \cup W]$. – Marco Gario Jul 18 '11 at 23:42