Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.
Is there a characterization of such graphs in the literature?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.Sign up to join this community
I don't know the answer for your question, but I know a somewhat related problem.
In this paper it is shown that, given a planar bipartite cubic graph $G$ and a set $W$ of vertices, it is NP-complete to decide if there is an induced tree containing the vertices in $W$. In this case, there is no restriction on the vertices outside the tree, and it can be the case where the structure you are looking for, being an independent set, helps.