Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.